1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2014 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"
72 #include "stor-layout.h"
73 #include "stringpool.h"
74 #include "print-tree.h"
75 #include "tree-inline.h"
76 #include "langhooks.h"
78 #include "diagnostic.h"
79 #include "gimple-pretty-print.h"
81 #include "tree-pass.h"
83 #include "basic-block.h"
84 #include "tree-ssa-alias.h"
85 #include "internal-fn.h"
86 #include "gimple-expr.h"
89 #include "gimple-iterator.h"
90 #include "gimple-ssa.h"
92 #include "tree-phinodes.h"
93 #include "ssa-iterators.h"
94 #include "tree-ssanames.h"
95 #include "tree-ssa-loop-niter.h"
96 #include "tree-ssa-loop.h"
98 #include "lto-streamer.h"
99 #include "data-streamer.h"
100 #include "tree-streamer.h"
101 #include "ipa-inline.h"
102 #include "alloc-pool.h"
104 #include "tree-scalar-evolution.h"
105 #include "ipa-utils.h"
107 #include "cfgexpand.h"
109 /* Estimate runtime of function can easilly run into huge numbers with many
110 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
111 integer. For anything larger we use gcov_type. */
112 #define MAX_TIME 500000
114 /* Number of bits in integer, but we really want to be stable across different
116 #define NUM_CONDITIONS 32
118 enum predicate_conditions
120 predicate_false_condition
= 0,
121 predicate_not_inlined_condition
= 1,
122 predicate_first_dynamic_condition
= 2
125 /* Special condition code we use to represent test that operand is compile time
127 #define IS_NOT_CONSTANT ERROR_MARK
128 /* Special condition code we use to represent test that operand is not changed
129 across invocation of the function. When operand IS_NOT_CONSTANT it is always
130 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
131 of executions even when they are not compile time constants. */
132 #define CHANGED IDENTIFIER_NODE
134 /* Holders of ipa cgraph hooks: */
135 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
136 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
137 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
138 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
139 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
140 static void inline_node_removal_hook (struct cgraph_node
*, void *);
141 static void inline_node_duplication_hook (struct cgraph_node
*,
142 struct cgraph_node
*, void *);
143 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
144 static void inline_edge_duplication_hook (struct cgraph_edge
*,
145 struct cgraph_edge
*, void *);
147 /* VECtor holding inline summaries.
148 In GGC memory because conditions might point to constant trees. */
149 vec
<inline_summary_t
, va_gc
> *inline_summary_vec
;
150 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
152 /* Cached node/edge growths. */
153 vec
<int> node_growth_cache
;
154 vec
<edge_growth_cache_entry
> edge_growth_cache
;
156 /* Edge predicates goes here. */
157 static alloc_pool edge_predicate_pool
;
159 /* Return true predicate (tautology).
160 We represent it by empty list of clauses. */
162 static inline struct predicate
163 true_predicate (void)
171 /* Return predicate testing single condition number COND. */
173 static inline struct predicate
174 single_cond_predicate (int cond
)
177 p
.clause
[0] = 1 << cond
;
183 /* Return false predicate. First clause require false condition. */
185 static inline struct predicate
186 false_predicate (void)
188 return single_cond_predicate (predicate_false_condition
);
192 /* Return true if P is (true). */
195 true_predicate_p (struct predicate
*p
)
197 return !p
->clause
[0];
201 /* Return true if P is (false). */
204 false_predicate_p (struct predicate
*p
)
206 if (p
->clause
[0] == (1 << predicate_false_condition
))
208 gcc_checking_assert (!p
->clause
[1]
209 && p
->clause
[0] == 1 << predicate_false_condition
);
216 /* Return predicate that is set true when function is not inlined. */
218 static inline struct predicate
219 not_inlined_predicate (void)
221 return single_cond_predicate (predicate_not_inlined_condition
);
224 /* Simple description of whether a memory load or a condition refers to a load
225 from an aggregate and if so, how and where from in the aggregate.
226 Individual fields have the same meaning like fields with the same name in
229 struct agg_position_info
231 HOST_WIDE_INT offset
;
236 /* Add condition to condition list CONDS. AGGPOS describes whether the used
237 oprand is loaded from an aggregate and where in the aggregate it is. It can
238 be NULL, which means this not a load from an aggregate. */
240 static struct predicate
241 add_condition (struct inline_summary
*summary
, int operand_num
,
242 struct agg_position_info
*aggpos
,
243 enum tree_code code
, tree val
)
247 struct condition new_cond
;
248 HOST_WIDE_INT offset
;
249 bool agg_contents
, by_ref
;
253 offset
= aggpos
->offset
;
254 agg_contents
= aggpos
->agg_contents
;
255 by_ref
= aggpos
->by_ref
;
260 agg_contents
= false;
264 gcc_checking_assert (operand_num
>= 0);
265 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
267 if (c
->operand_num
== operand_num
270 && c
->agg_contents
== agg_contents
271 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
272 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
274 /* Too many conditions. Give up and return constant true. */
275 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
276 return true_predicate ();
278 new_cond
.operand_num
= operand_num
;
279 new_cond
.code
= code
;
281 new_cond
.agg_contents
= agg_contents
;
282 new_cond
.by_ref
= by_ref
;
283 new_cond
.offset
= offset
;
284 vec_safe_push (summary
->conds
, new_cond
);
285 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
289 /* Add clause CLAUSE into the predicate P. */
292 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
296 int insert_here
= -1;
303 /* False clause makes the whole predicate false. Kill the other variants. */
304 if (clause
== (1 << predicate_false_condition
))
306 p
->clause
[0] = (1 << predicate_false_condition
);
310 if (false_predicate_p (p
))
313 /* No one should be silly enough to add false into nontrivial clauses. */
314 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
316 /* Look where to insert the clause. At the same time prune out
317 clauses of P that are implied by the new clause and thus
319 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
321 p
->clause
[i2
] = p
->clause
[i
];
326 /* If p->clause[i] implies clause, there is nothing to add. */
327 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
329 /* We had nothing to add, none of clauses should've become
331 gcc_checking_assert (i
== i2
);
335 if (p
->clause
[i
] < clause
&& insert_here
< 0)
338 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
339 Otherwise the p->clause[i] has to stay. */
340 if ((p
->clause
[i
] & clause
) != clause
)
344 /* Look for clauses that are obviously true. I.e.
345 op0 == 5 || op0 != 5. */
346 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
349 if (!(clause
& (1 << c1
)))
351 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
352 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
353 and thus there is no point for looking for them. */
354 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
356 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
357 if (clause
& (1 << c2
))
360 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
362 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
363 if (cc1
->operand_num
== cc2
->operand_num
364 && cc1
->val
== cc2
->val
365 && cc2
->code
!= IS_NOT_CONSTANT
366 && cc2
->code
!= CHANGED
367 && cc1
->code
== invert_tree_comparison
369 HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1
->val
)))))
375 /* We run out of variants. Be conservative in positive direction. */
376 if (i2
== MAX_CLAUSES
)
378 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
379 p
->clause
[i2
+ 1] = 0;
380 if (insert_here
>= 0)
381 for (; i2
> insert_here
; i2
--)
382 p
->clause
[i2
] = p
->clause
[i2
- 1];
385 p
->clause
[insert_here
] = clause
;
391 static struct predicate
392 and_predicates (conditions conditions
,
393 struct predicate
*p
, struct predicate
*p2
)
395 struct predicate out
= *p
;
398 /* Avoid busy work. */
399 if (false_predicate_p (p2
) || true_predicate_p (p
))
401 if (false_predicate_p (p
) || true_predicate_p (p2
))
404 /* See how far predicates match. */
405 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
407 gcc_checking_assert (i
< MAX_CLAUSES
);
410 /* Combine the predicates rest. */
411 for (; p2
->clause
[i
]; i
++)
413 gcc_checking_assert (i
< MAX_CLAUSES
);
414 add_clause (conditions
, &out
, p2
->clause
[i
]);
420 /* Return true if predicates are obviously equal. */
423 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
426 for (i
= 0; p
->clause
[i
]; i
++)
428 gcc_checking_assert (i
< MAX_CLAUSES
);
429 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
430 gcc_checking_assert (!p2
->clause
[i
]
431 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
432 if (p
->clause
[i
] != p2
->clause
[i
])
435 return !p2
->clause
[i
];
441 static struct predicate
442 or_predicates (conditions conditions
,
443 struct predicate
*p
, struct predicate
*p2
)
445 struct predicate out
= true_predicate ();
448 /* Avoid busy work. */
449 if (false_predicate_p (p2
) || true_predicate_p (p
))
451 if (false_predicate_p (p
) || true_predicate_p (p2
))
453 if (predicates_equal_p (p
, p2
))
456 /* OK, combine the predicates. */
457 for (i
= 0; p
->clause
[i
]; i
++)
458 for (j
= 0; p2
->clause
[j
]; j
++)
460 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
461 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
467 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
468 if predicate P is known to be false. */
471 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
475 /* True remains true. */
476 if (true_predicate_p (p
))
479 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
481 /* See if we can find clause we can disprove. */
482 for (i
= 0; p
->clause
[i
]; i
++)
484 gcc_checking_assert (i
< MAX_CLAUSES
);
485 if (!(p
->clause
[i
] & possible_truths
))
491 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
492 instruction will be recomputed per invocation of the inlined call. */
495 predicate_probability (conditions conds
,
496 struct predicate
*p
, clause_t possible_truths
,
497 vec
<inline_param_summary
> inline_param_summary
)
500 int combined_prob
= REG_BR_PROB_BASE
;
502 /* True remains true. */
503 if (true_predicate_p (p
))
504 return REG_BR_PROB_BASE
;
506 if (false_predicate_p (p
))
509 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
511 /* See if we can find clause we can disprove. */
512 for (i
= 0; p
->clause
[i
]; i
++)
514 gcc_checking_assert (i
< MAX_CLAUSES
);
515 if (!(p
->clause
[i
] & possible_truths
))
521 if (!inline_param_summary
.exists ())
522 return REG_BR_PROB_BASE
;
523 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
524 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
526 if (i2
>= predicate_first_dynamic_condition
)
529 &(*conds
)[i2
- predicate_first_dynamic_condition
];
530 if (c
->code
== CHANGED
532 (int) inline_param_summary
.length ()))
535 inline_param_summary
[c
->operand_num
].change_prob
;
536 this_prob
= MAX (this_prob
, iprob
);
539 this_prob
= REG_BR_PROB_BASE
;
542 this_prob
= REG_BR_PROB_BASE
;
544 combined_prob
= MIN (this_prob
, combined_prob
);
549 return combined_prob
;
553 /* Dump conditional COND. */
556 dump_condition (FILE *f
, conditions conditions
, int cond
)
559 if (cond
== predicate_false_condition
)
560 fprintf (f
, "false");
561 else if (cond
== predicate_not_inlined_condition
)
562 fprintf (f
, "not inlined");
565 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
566 fprintf (f
, "op%i", c
->operand_num
);
568 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
569 c
->by_ref
? "ref " : "", c
->offset
);
570 if (c
->code
== IS_NOT_CONSTANT
)
572 fprintf (f
, " not constant");
575 if (c
->code
== CHANGED
)
577 fprintf (f
, " changed");
580 fprintf (f
, " %s ", op_symbol_code (c
->code
));
581 print_generic_expr (f
, c
->val
, 1);
586 /* Dump clause CLAUSE. */
589 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
596 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
597 if (clause
& (1 << i
))
602 dump_condition (f
, conds
, i
);
608 /* Dump predicate PREDICATE. */
611 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
614 if (true_predicate_p (pred
))
615 dump_clause (f
, conds
, 0);
617 for (i
= 0; pred
->clause
[i
]; i
++)
621 dump_clause (f
, conds
, pred
->clause
[i
]);
627 /* Dump inline hints. */
629 dump_inline_hints (FILE *f
, inline_hints hints
)
633 fprintf (f
, "inline hints:");
634 if (hints
& INLINE_HINT_indirect_call
)
636 hints
&= ~INLINE_HINT_indirect_call
;
637 fprintf (f
, " indirect_call");
639 if (hints
& INLINE_HINT_loop_iterations
)
641 hints
&= ~INLINE_HINT_loop_iterations
;
642 fprintf (f
, " loop_iterations");
644 if (hints
& INLINE_HINT_loop_stride
)
646 hints
&= ~INLINE_HINT_loop_stride
;
647 fprintf (f
, " loop_stride");
649 if (hints
& INLINE_HINT_same_scc
)
651 hints
&= ~INLINE_HINT_same_scc
;
652 fprintf (f
, " same_scc");
654 if (hints
& INLINE_HINT_in_scc
)
656 hints
&= ~INLINE_HINT_in_scc
;
657 fprintf (f
, " in_scc");
659 if (hints
& INLINE_HINT_cross_module
)
661 hints
&= ~INLINE_HINT_cross_module
;
662 fprintf (f
, " cross_module");
664 if (hints
& INLINE_HINT_declared_inline
)
666 hints
&= ~INLINE_HINT_declared_inline
;
667 fprintf (f
, " declared_inline");
669 if (hints
& INLINE_HINT_array_index
)
671 hints
&= ~INLINE_HINT_array_index
;
672 fprintf (f
, " array_index");
674 if (hints
& INLINE_HINT_known_hot
)
676 hints
&= ~INLINE_HINT_known_hot
;
677 fprintf (f
, " known_hot");
683 /* Record SIZE and TIME under condition PRED into the inline summary. */
686 account_size_time (struct inline_summary
*summary
, int size
, int time
,
687 struct predicate
*pred
)
693 if (false_predicate_p (pred
))
696 /* We need to create initial empty unconitional clause, but otherwie
697 we don't need to account empty times and sizes. */
698 if (!size
&& !time
&& summary
->entry
)
701 /* Watch overflow that might result from insane profiles. */
702 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
703 time
= MAX_TIME
* INLINE_TIME_SCALE
;
704 gcc_assert (time
>= 0);
706 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
707 if (predicates_equal_p (&e
->predicate
, pred
))
716 e
= &(*summary
->entry
)[0];
717 gcc_assert (!e
->predicate
.clause
[0]);
718 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
720 "\t\tReached limit on number of entries, "
721 "ignoring the predicate.");
723 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
726 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
727 ((double) size
) / INLINE_SIZE_SCALE
,
728 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
729 dump_predicate (dump_file
, summary
->conds
, pred
);
733 struct size_time_entry new_entry
;
734 new_entry
.size
= size
;
735 new_entry
.time
= time
;
736 new_entry
.predicate
= *pred
;
737 vec_safe_push (summary
->entry
, new_entry
);
743 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
744 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
748 /* Set predicate for edge E. */
751 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
753 struct inline_edge_summary
*es
= inline_edge_summary (e
);
755 /* If the edge is determined to be never executed, redirect it
756 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
757 if (predicate
&& false_predicate_p (predicate
) && e
->callee
)
759 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
761 e
->redirect_callee (cgraph_node::get_create
762 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
)));
763 e
->inline_failed
= CIF_UNREACHABLE
;
765 callee
->remove_symbol_and_inline_clones ();
767 if (predicate
&& !true_predicate_p (predicate
))
770 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
771 *es
->predicate
= *predicate
;
776 pool_free (edge_predicate_pool
, es
->predicate
);
777 es
->predicate
= NULL
;
781 /* Set predicate for hint *P. */
784 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
786 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
789 pool_free (edge_predicate_pool
, *p
);
795 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
801 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
802 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
803 Return clause of possible truths. When INLINE_P is true, assume that we are
806 ERROR_MARK means compile time invariant. */
809 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
811 vec
<tree
> known_vals
,
812 vec
<ipa_agg_jump_function_p
>
815 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
816 struct inline_summary
*info
= inline_summary (node
);
820 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
825 /* We allow call stmt to have fewer arguments than the callee function
826 (especially for K&R style programs). So bound check here (we assume
827 known_aggs vector, if non-NULL, has the same length as
829 gcc_checking_assert (!known_aggs
.exists ()
830 || (known_vals
.length () == known_aggs
.length ()));
831 if (c
->operand_num
>= (int) known_vals
.length ())
833 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
839 struct ipa_agg_jump_function
*agg
;
841 if (c
->code
== CHANGED
843 && (known_vals
[c
->operand_num
] == error_mark_node
))
846 if (known_aggs
.exists ())
848 agg
= known_aggs
[c
->operand_num
];
849 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
856 val
= known_vals
[c
->operand_num
];
857 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
863 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
866 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
868 res
= fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
);
869 if (res
&& integer_zerop (res
))
871 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
877 /* Work out what conditions might be true at invocation of E. */
880 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
881 clause_t
*clause_ptr
,
882 vec
<tree
> *known_vals_ptr
,
883 vec
<tree
> *known_binfos_ptr
,
884 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
886 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
887 struct inline_summary
*info
= inline_summary (callee
);
888 vec
<tree
> known_vals
= vNULL
;
889 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
892 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
894 known_vals_ptr
->create (0);
895 if (known_binfos_ptr
)
896 known_binfos_ptr
->create (0);
898 if (ipa_node_params_vector
.exists ()
899 && !e
->call_stmt_cannot_inline_p
900 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_binfos_ptr
))
902 struct ipa_node_params
*parms_info
;
903 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
904 struct inline_edge_summary
*es
= inline_edge_summary (e
);
905 int i
, count
= ipa_get_cs_argument_count (args
);
907 if (e
->caller
->global
.inlined_to
)
908 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
910 parms_info
= IPA_NODE_REF (e
->caller
);
912 if (count
&& (info
->conds
|| known_vals_ptr
))
913 known_vals
.safe_grow_cleared (count
);
914 if (count
&& (info
->conds
|| known_aggs_ptr
))
915 known_aggs
.safe_grow_cleared (count
);
916 if (count
&& known_binfos_ptr
)
917 known_binfos_ptr
->safe_grow_cleared (count
);
919 for (i
= 0; i
< count
; i
++)
921 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
922 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
925 if (known_vals
.exists () && TREE_CODE (cst
) != TREE_BINFO
)
927 else if (known_binfos_ptr
!= NULL
928 && TREE_CODE (cst
) == TREE_BINFO
)
929 (*known_binfos_ptr
)[i
] = cst
;
931 else if (inline_p
&& !es
->param
[i
].change_prob
)
932 known_vals
[i
] = error_mark_node
;
933 /* TODO: When IPA-CP starts propagating and merging aggregate jump
934 functions, use its knowledge of the caller too, just like the
935 scalar case above. */
936 known_aggs
[i
] = &jf
->agg
;
941 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
942 known_vals
, known_aggs
);
945 *known_vals_ptr
= known_vals
;
947 known_vals
.release ();
950 *known_aggs_ptr
= known_aggs
;
952 known_aggs
.release ();
956 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
959 inline_summary_alloc (void)
961 if (!node_removal_hook_holder
)
962 node_removal_hook_holder
=
963 symtab
->add_cgraph_removal_hook (&inline_node_removal_hook
, NULL
);
964 if (!edge_removal_hook_holder
)
965 edge_removal_hook_holder
=
966 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
967 if (!node_duplication_hook_holder
)
968 node_duplication_hook_holder
=
969 symtab
->add_cgraph_duplication_hook (&inline_node_duplication_hook
, NULL
);
970 if (!edge_duplication_hook_holder
)
971 edge_duplication_hook_holder
=
972 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
974 if (vec_safe_length (inline_summary_vec
) <= (unsigned) symtab
->cgraph_max_uid
)
975 vec_safe_grow_cleared (inline_summary_vec
, symtab
->cgraph_max_uid
+ 1);
976 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
977 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
978 if (!edge_predicate_pool
)
979 edge_predicate_pool
= create_alloc_pool ("edge predicates",
980 sizeof (struct predicate
), 10);
983 /* We are called multiple time for given function; clear
984 data from previous run so they are not cumulated. */
987 reset_inline_edge_summary (struct cgraph_edge
*e
)
989 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
991 struct inline_edge_summary
*es
= inline_edge_summary (e
);
993 es
->call_stmt_size
= es
->call_stmt_time
= 0;
995 pool_free (edge_predicate_pool
, es
->predicate
);
996 es
->predicate
= NULL
;
997 es
->param
.release ();
1001 /* We are called multiple time for given function; clear
1002 data from previous run so they are not cumulated. */
1005 reset_inline_summary (struct cgraph_node
*node
)
1007 struct inline_summary
*info
= inline_summary (node
);
1008 struct cgraph_edge
*e
;
1010 info
->self_size
= info
->self_time
= 0;
1011 info
->estimated_stack_size
= 0;
1012 info
->estimated_self_stack_size
= 0;
1013 info
->stack_frame_offset
= 0;
1018 if (info
->loop_iterations
)
1020 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1021 info
->loop_iterations
= NULL
;
1023 if (info
->loop_stride
)
1025 pool_free (edge_predicate_pool
, info
->loop_stride
);
1026 info
->loop_stride
= NULL
;
1028 if (info
->array_index
)
1030 pool_free (edge_predicate_pool
, info
->array_index
);
1031 info
->array_index
= NULL
;
1033 vec_free (info
->conds
);
1034 vec_free (info
->entry
);
1035 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1036 reset_inline_edge_summary (e
);
1037 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1038 reset_inline_edge_summary (e
);
1041 /* Hook that is called by cgraph.c when a node is removed. */
1044 inline_node_removal_hook (struct cgraph_node
*node
,
1045 void *data ATTRIBUTE_UNUSED
)
1047 struct inline_summary
*info
;
1048 if (vec_safe_length (inline_summary_vec
) <= (unsigned) node
->uid
)
1050 info
= inline_summary (node
);
1051 reset_inline_summary (node
);
1052 memset (info
, 0, sizeof (inline_summary_t
));
1055 /* Remap predicate P of former function to be predicate of duplicated function.
1056 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1057 INFO is inline summary of the duplicated node. */
1059 static struct predicate
1060 remap_predicate_after_duplication (struct predicate
*p
,
1061 clause_t possible_truths
,
1062 struct inline_summary
*info
)
1064 struct predicate new_predicate
= true_predicate ();
1066 for (j
= 0; p
->clause
[j
]; j
++)
1067 if (!(possible_truths
& p
->clause
[j
]))
1069 new_predicate
= false_predicate ();
1073 add_clause (info
->conds
, &new_predicate
,
1074 possible_truths
& p
->clause
[j
]);
1075 return new_predicate
;
1078 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1079 Additionally care about allocating new memory slot for updated predicate
1080 and set it to NULL when it becomes true or false (and thus uninteresting).
1084 remap_hint_predicate_after_duplication (struct predicate
**p
,
1085 clause_t possible_truths
,
1086 struct inline_summary
*info
)
1088 struct predicate new_predicate
;
1093 new_predicate
= remap_predicate_after_duplication (*p
,
1094 possible_truths
, info
);
1095 /* We do not want to free previous predicate; it is used by node origin. */
1097 set_hint_predicate (p
, new_predicate
);
1101 /* Hook that is called by cgraph.c when a node is duplicated. */
1104 inline_node_duplication_hook (struct cgraph_node
*src
,
1105 struct cgraph_node
*dst
,
1106 ATTRIBUTE_UNUSED
void *data
)
1108 struct inline_summary
*info
;
1109 inline_summary_alloc ();
1110 info
= inline_summary (dst
);
1111 memcpy (info
, inline_summary (src
), sizeof (struct inline_summary
));
1112 /* TODO: as an optimization, we may avoid copying conditions
1113 that are known to be false or true. */
1114 info
->conds
= vec_safe_copy (info
->conds
);
1116 /* When there are any replacements in the function body, see if we can figure
1117 out that something was optimized out. */
1118 if (ipa_node_params_vector
.exists () && dst
->clone
.tree_map
)
1120 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1121 /* Use SRC parm info since it may not be copied yet. */
1122 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1123 vec
<tree
> known_vals
= vNULL
;
1124 int count
= ipa_get_param_count (parms_info
);
1126 clause_t possible_truths
;
1127 struct predicate true_pred
= true_predicate ();
1129 int optimized_out_size
= 0;
1130 bool inlined_to_p
= false;
1131 struct cgraph_edge
*edge
;
1134 known_vals
.safe_grow_cleared (count
);
1135 for (i
= 0; i
< count
; i
++)
1137 struct ipa_replace_map
*r
;
1139 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1141 if (((!r
->old_tree
&& r
->parm_num
== i
)
1142 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1143 && r
->replace_p
&& !r
->ref_p
)
1145 known_vals
[i
] = r
->new_tree
;
1150 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1153 known_vals
.release ();
1155 account_size_time (info
, 0, 0, &true_pred
);
1157 /* Remap size_time vectors.
1158 Simplify the predicate by prunning out alternatives that are known
1160 TODO: as on optimization, we can also eliminate conditions known
1162 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1164 struct predicate new_predicate
;
1165 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1168 if (false_predicate_p (&new_predicate
))
1169 optimized_out_size
+= e
->size
;
1171 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1174 /* Remap edge predicates with the same simplification as above.
1175 Also copy constantness arrays. */
1176 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1178 struct predicate new_predicate
;
1179 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1181 if (!edge
->inline_failed
)
1182 inlined_to_p
= true;
1185 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1188 if (false_predicate_p (&new_predicate
)
1189 && !false_predicate_p (es
->predicate
))
1191 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1192 edge
->frequency
= 0;
1194 edge_set_predicate (edge
, &new_predicate
);
1197 /* Remap indirect edge predicates with the same simplificaiton as above.
1198 Also copy constantness arrays. */
1199 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1201 struct predicate new_predicate
;
1202 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1204 gcc_checking_assert (edge
->inline_failed
);
1207 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1210 if (false_predicate_p (&new_predicate
)
1211 && !false_predicate_p (es
->predicate
))
1213 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1214 edge
->frequency
= 0;
1216 edge_set_predicate (edge
, &new_predicate
);
1218 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1219 possible_truths
, info
);
1220 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1221 possible_truths
, info
);
1222 remap_hint_predicate_after_duplication (&info
->array_index
,
1223 possible_truths
, info
);
1225 /* If inliner or someone after inliner will ever start producing
1226 non-trivial clones, we will get trouble with lack of information
1227 about updating self sizes, because size vectors already contains
1228 sizes of the calees. */
1229 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1233 info
->entry
= vec_safe_copy (info
->entry
);
1234 if (info
->loop_iterations
)
1236 predicate p
= *info
->loop_iterations
;
1237 info
->loop_iterations
= NULL
;
1238 set_hint_predicate (&info
->loop_iterations
, p
);
1240 if (info
->loop_stride
)
1242 predicate p
= *info
->loop_stride
;
1243 info
->loop_stride
= NULL
;
1244 set_hint_predicate (&info
->loop_stride
, p
);
1246 if (info
->array_index
)
1248 predicate p
= *info
->array_index
;
1249 info
->array_index
= NULL
;
1250 set_hint_predicate (&info
->array_index
, p
);
1253 inline_update_overall_summary (dst
);
1257 /* Hook that is called by cgraph.c when a node is duplicated. */
1260 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1261 struct cgraph_edge
*dst
,
1262 ATTRIBUTE_UNUSED
void *data
)
1264 struct inline_edge_summary
*info
;
1265 struct inline_edge_summary
*srcinfo
;
1266 inline_summary_alloc ();
1267 info
= inline_edge_summary (dst
);
1268 srcinfo
= inline_edge_summary (src
);
1269 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1270 info
->predicate
= NULL
;
1271 edge_set_predicate (dst
, srcinfo
->predicate
);
1272 info
->param
= srcinfo
->param
.copy ();
1276 /* Keep edge cache consistent across edge removal. */
1279 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1280 void *data ATTRIBUTE_UNUSED
)
1282 if (edge_growth_cache
.exists ())
1283 reset_edge_growth_cache (edge
);
1284 reset_inline_edge_summary (edge
);
1288 /* Initialize growth caches. */
1291 initialize_growth_caches (void)
1293 if (symtab
->edges_max_uid
)
1294 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1295 if (symtab
->cgraph_max_uid
)
1296 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
1300 /* Free growth caches. */
1303 free_growth_caches (void)
1305 edge_growth_cache
.release ();
1306 node_growth_cache
.release ();
1310 /* Dump edge summaries associated to NODE and recursively to all clones.
1311 Indent by INDENT. */
1314 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1315 struct inline_summary
*info
)
1317 struct cgraph_edge
*edge
;
1318 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1320 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1321 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1325 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1326 " time: %2i callee size:%2i stack:%2i",
1327 indent
, "", callee
->name (), callee
->order
,
1328 !edge
->inline_failed
1329 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1330 indent
, "", es
->loop_depth
, edge
->frequency
,
1331 es
->call_stmt_size
, es
->call_stmt_time
,
1332 (int) inline_summary (callee
)->size
/ INLINE_SIZE_SCALE
,
1333 (int) inline_summary (callee
)->estimated_stack_size
);
1337 fprintf (f
, " predicate: ");
1338 dump_predicate (f
, info
->conds
, es
->predicate
);
1342 if (es
->param
.exists ())
1343 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1345 int prob
= es
->param
[i
].change_prob
;
1348 fprintf (f
, "%*s op%i is compile time invariant\n",
1350 else if (prob
!= REG_BR_PROB_BASE
)
1351 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1352 prob
* 100.0 / REG_BR_PROB_BASE
);
1354 if (!edge
->inline_failed
)
1356 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1357 " callee size %i\n",
1359 (int) inline_summary (callee
)->stack_frame_offset
,
1360 (int) inline_summary (callee
)->estimated_self_stack_size
,
1361 (int) inline_summary (callee
)->estimated_stack_size
);
1362 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1365 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1367 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1368 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1372 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1375 fprintf (f
, "predicate: ");
1376 dump_predicate (f
, info
->conds
, es
->predicate
);
1385 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1387 if (node
->definition
)
1389 struct inline_summary
*s
= inline_summary (node
);
1392 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1394 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1395 fprintf (f
, " always_inline");
1397 fprintf (f
, " inlinable");
1398 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1399 fprintf (f
, " global time: %i\n", s
->time
);
1400 fprintf (f
, " self size: %i\n", s
->self_size
);
1401 fprintf (f
, " global size: %i\n", s
->size
);
1402 fprintf (f
, " min size: %i\n", s
->min_size
);
1403 fprintf (f
, " self stack: %i\n",
1404 (int) s
->estimated_self_stack_size
);
1405 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1407 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1409 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1410 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1412 fprintf (f
, " size:%f, time:%f, predicate:",
1413 (double) e
->size
/ INLINE_SIZE_SCALE
,
1414 (double) e
->time
/ INLINE_TIME_SCALE
);
1415 dump_predicate (f
, s
->conds
, &e
->predicate
);
1417 if (s
->loop_iterations
)
1419 fprintf (f
, " loop iterations:");
1420 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1424 fprintf (f
, " loop stride:");
1425 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1429 fprintf (f
, " array index:");
1430 dump_predicate (f
, s
->conds
, s
->array_index
);
1432 fprintf (f
, " calls:\n");
1433 dump_inline_edge_summary (f
, 4, node
, s
);
1439 debug_inline_summary (struct cgraph_node
*node
)
1441 dump_inline_summary (stderr
, node
);
1445 dump_inline_summaries (FILE *f
)
1447 struct cgraph_node
*node
;
1449 FOR_EACH_DEFINED_FUNCTION (node
)
1450 if (!node
->global
.inlined_to
)
1451 dump_inline_summary (f
, node
);
1454 /* Give initial reasons why inlining would fail on EDGE. This gets either
1455 nullified or usually overwritten by more precise reasons later. */
1458 initialize_inline_failed (struct cgraph_edge
*e
)
1460 struct cgraph_node
*callee
= e
->callee
;
1462 if (e
->indirect_unknown_callee
)
1463 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1464 else if (!callee
->definition
)
1465 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1466 else if (callee
->local
.redefined_extern_inline
)
1467 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1468 else if (e
->call_stmt_cannot_inline_p
)
1469 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1470 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1471 /* We can't inline if the function is spawing a function. */
1472 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1474 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1477 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1478 boolean variable pointed to by DATA. */
1481 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1484 bool *b
= (bool *) data
;
1489 /* If OP refers to value of function parameter, return the corresponding
1493 unmodified_parm_1 (gimple stmt
, tree op
)
1495 /* SSA_NAME referring to parm default def? */
1496 if (TREE_CODE (op
) == SSA_NAME
1497 && SSA_NAME_IS_DEFAULT_DEF (op
)
1498 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1499 return SSA_NAME_VAR (op
);
1500 /* Non-SSA parm reference? */
1501 if (TREE_CODE (op
) == PARM_DECL
)
1503 bool modified
= false;
1506 ao_ref_init (&refd
, op
);
1507 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1515 /* If OP refers to value of function parameter, return the corresponding
1516 parameter. Also traverse chains of SSA register assignments. */
1519 unmodified_parm (gimple stmt
, tree op
)
1521 tree res
= unmodified_parm_1 (stmt
, op
);
1525 if (TREE_CODE (op
) == SSA_NAME
1526 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1527 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1528 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1529 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1533 /* If OP refers to a value of a function parameter or value loaded from an
1534 aggregate passed to a parameter (either by value or reference), return TRUE
1535 and store the number of the parameter to *INDEX_P and information whether
1536 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1537 the function parameters, STMT is the statement in which OP is used or
1541 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1542 gimple stmt
, tree op
, int *index_p
,
1543 struct agg_position_info
*aggpos
)
1545 tree res
= unmodified_parm_1 (stmt
, op
);
1547 gcc_checking_assert (aggpos
);
1550 *index_p
= ipa_get_param_decl_index (info
, res
);
1553 aggpos
->agg_contents
= false;
1554 aggpos
->by_ref
= false;
1558 if (TREE_CODE (op
) == SSA_NAME
)
1560 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1561 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1563 stmt
= SSA_NAME_DEF_STMT (op
);
1564 op
= gimple_assign_rhs1 (stmt
);
1565 if (!REFERENCE_CLASS_P (op
))
1566 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1570 aggpos
->agg_contents
= true;
1571 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1575 /* See if statement might disappear after inlining.
1576 0 - means not eliminated
1577 1 - half of statements goes away
1578 2 - for sure it is eliminated.
1579 We are not terribly sophisticated, basically looking for simple abstraction
1580 penalty wrappers. */
1583 eliminated_by_inlining_prob (gimple stmt
)
1585 enum gimple_code code
= gimple_code (stmt
);
1586 enum tree_code rhs_code
;
1596 if (gimple_num_ops (stmt
) != 2)
1599 rhs_code
= gimple_assign_rhs_code (stmt
);
1601 /* Casts of parameters, loads from parameters passed by reference
1602 and stores to return value or parameters are often free after
1603 inlining dua to SRA and further combining.
1604 Assume that half of statements goes away. */
1605 if (rhs_code
== CONVERT_EXPR
1606 || rhs_code
== NOP_EXPR
1607 || rhs_code
== VIEW_CONVERT_EXPR
1608 || rhs_code
== ADDR_EXPR
1609 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1611 tree rhs
= gimple_assign_rhs1 (stmt
);
1612 tree lhs
= gimple_assign_lhs (stmt
);
1613 tree inner_rhs
= get_base_address (rhs
);
1614 tree inner_lhs
= get_base_address (lhs
);
1615 bool rhs_free
= false;
1616 bool lhs_free
= false;
1623 /* Reads of parameter are expected to be free. */
1624 if (unmodified_parm (stmt
, inner_rhs
))
1626 /* Match expressions of form &this->field. Those will most likely
1627 combine with something upstream after inlining. */
1628 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1630 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1631 if (TREE_CODE (op
) == PARM_DECL
)
1633 else if (TREE_CODE (op
) == MEM_REF
1634 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1638 /* When parameter is not SSA register because its address is taken
1639 and it is just copied into one, the statement will be completely
1640 free after inlining (we will copy propagate backward). */
1641 if (rhs_free
&& is_gimple_reg (lhs
))
1644 /* Reads of parameters passed by reference
1645 expected to be free (i.e. optimized out after inlining). */
1646 if (TREE_CODE (inner_rhs
) == MEM_REF
1647 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1650 /* Copying parameter passed by reference into gimple register is
1651 probably also going to copy propagate, but we can't be quite
1653 if (rhs_free
&& is_gimple_reg (lhs
))
1656 /* Writes to parameters, parameters passed by value and return value
1657 (either dirrectly or passed via invisible reference) are free.
1659 TODO: We ought to handle testcase like
1660 struct a {int a,b;};
1662 retrurnsturct (void)
1668 This translate into:
1683 For that we either need to copy ipa-split logic detecting writes
1685 if (TREE_CODE (inner_lhs
) == PARM_DECL
1686 || TREE_CODE (inner_lhs
) == RESULT_DECL
1687 || (TREE_CODE (inner_lhs
) == MEM_REF
1688 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1689 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1690 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1691 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1693 0))) == RESULT_DECL
))))
1696 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1698 if (lhs_free
&& rhs_free
)
1708 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1709 predicates to the CFG edges. */
1712 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1713 struct inline_summary
*summary
,
1719 struct agg_position_info aggpos
;
1720 enum tree_code code
, inverted_code
;
1726 last
= last_stmt (bb
);
1727 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1729 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1731 op
= gimple_cond_lhs (last
);
1732 /* TODO: handle conditionals like
1735 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1737 code
= gimple_cond_code (last
);
1739 = invert_tree_comparison (code
,
1740 HONOR_NANS (TYPE_MODE (TREE_TYPE (op
))));
1742 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1744 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1745 ? code
: inverted_code
);
1746 /* invert_tree_comparison will return ERROR_MARK on FP
1747 comparsions that are not EQ/NE instead of returning proper
1748 unordered one. Be sure it is not confused with NON_CONSTANT. */
1749 if (this_code
!= ERROR_MARK
)
1751 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1753 gimple_cond_rhs (last
));
1754 e
->aux
= pool_alloc (edge_predicate_pool
);
1755 *(struct predicate
*) e
->aux
= p
;
1760 if (TREE_CODE (op
) != SSA_NAME
)
1763 if (builtin_constant_p (op))
1767 Here we can predicate nonconstant_code. We can't
1768 really handle constant_code since we have no predicate
1769 for this and also the constant code is not known to be
1770 optimized away when inliner doen't see operand is constant.
1771 Other optimizers might think otherwise. */
1772 if (gimple_cond_code (last
) != NE_EXPR
1773 || !integer_zerop (gimple_cond_rhs (last
)))
1775 set_stmt
= SSA_NAME_DEF_STMT (op
);
1776 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1777 || gimple_call_num_args (set_stmt
) != 1)
1779 op2
= gimple_call_arg (set_stmt
, 0);
1780 if (!unmodified_parm_or_parm_agg_item
1781 (info
, set_stmt
, op2
, &index
, &aggpos
))
1783 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1785 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1786 IS_NOT_CONSTANT
, NULL_TREE
);
1787 e
->aux
= pool_alloc (edge_predicate_pool
);
1788 *(struct predicate
*) e
->aux
= p
;
1793 /* If BB ends by a switch we can turn into predicates, attach corresponding
1794 predicates to the CFG edges. */
1797 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1798 struct inline_summary
*summary
,
1804 struct agg_position_info aggpos
;
1810 lastg
= last_stmt (bb
);
1811 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1813 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1814 op
= gimple_switch_index (last
);
1815 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1818 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1820 e
->aux
= pool_alloc (edge_predicate_pool
);
1821 *(struct predicate
*) e
->aux
= false_predicate ();
1823 n
= gimple_switch_num_labels (last
);
1824 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1826 tree cl
= gimple_switch_label (last
, case_idx
);
1830 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1831 min
= CASE_LOW (cl
);
1832 max
= CASE_HIGH (cl
);
1834 /* For default we might want to construct predicate that none
1835 of cases is met, but it is bit hard to do not having negations
1836 of conditionals handy. */
1838 p
= true_predicate ();
1840 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1843 struct predicate p1
, p2
;
1844 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1845 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1846 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1848 *(struct predicate
*) e
->aux
1849 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1854 /* For each BB in NODE attach to its AUX pointer predicate under
1855 which it is executable. */
1858 compute_bb_predicates (struct cgraph_node
*node
,
1859 struct ipa_node_params
*parms_info
,
1860 struct inline_summary
*summary
)
1862 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1866 FOR_EACH_BB_FN (bb
, my_function
)
1868 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1869 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1872 /* Entry block is always executable. */
1873 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1874 = pool_alloc (edge_predicate_pool
);
1875 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1876 = true_predicate ();
1878 /* A simple dataflow propagation of predicates forward in the CFG.
1879 TODO: work in reverse postorder. */
1883 FOR_EACH_BB_FN (bb
, my_function
)
1885 struct predicate p
= false_predicate ();
1888 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1892 struct predicate this_bb_predicate
1893 = *(struct predicate
*) e
->src
->aux
;
1896 = and_predicates (summary
->conds
, &this_bb_predicate
,
1897 (struct predicate
*) e
->aux
);
1898 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1899 if (true_predicate_p (&p
))
1903 if (false_predicate_p (&p
))
1904 gcc_assert (!bb
->aux
);
1910 bb
->aux
= pool_alloc (edge_predicate_pool
);
1911 *((struct predicate
*) bb
->aux
) = p
;
1913 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1915 /* This OR operation is needed to ensure monotonous data flow
1916 in the case we hit the limit on number of clauses and the
1917 and/or operations above give approximate answers. */
1918 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1919 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1922 *((struct predicate
*) bb
->aux
) = p
;
1931 /* We keep info about constantness of SSA names. */
1933 typedef struct predicate predicate_t
;
1934 /* Return predicate specifying when the STMT might have result that is not
1935 a compile time constant. */
1937 static struct predicate
1938 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1939 struct inline_summary
*summary
,
1941 vec
<predicate_t
> nonconstant_names
)
1946 while (UNARY_CLASS_P (expr
))
1947 expr
= TREE_OPERAND (expr
, 0);
1949 parm
= unmodified_parm (NULL
, expr
);
1950 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1951 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1952 if (is_gimple_min_invariant (expr
))
1953 return false_predicate ();
1954 if (TREE_CODE (expr
) == SSA_NAME
)
1955 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1956 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1958 struct predicate p1
= will_be_nonconstant_expr_predicate
1959 (info
, summary
, TREE_OPERAND (expr
, 0),
1961 struct predicate p2
;
1962 if (true_predicate_p (&p1
))
1964 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1965 TREE_OPERAND (expr
, 1),
1967 return or_predicates (summary
->conds
, &p1
, &p2
);
1969 else if (TREE_CODE (expr
) == COND_EXPR
)
1971 struct predicate p1
= will_be_nonconstant_expr_predicate
1972 (info
, summary
, TREE_OPERAND (expr
, 0),
1974 struct predicate p2
;
1975 if (true_predicate_p (&p1
))
1977 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1978 TREE_OPERAND (expr
, 1),
1980 if (true_predicate_p (&p2
))
1982 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
1983 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1984 TREE_OPERAND (expr
, 2),
1986 return or_predicates (summary
->conds
, &p1
, &p2
);
1993 return false_predicate ();
1997 /* Return predicate specifying when the STMT might have result that is not
1998 a compile time constant. */
2000 static struct predicate
2001 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2002 struct inline_summary
*summary
,
2004 vec
<predicate_t
> nonconstant_names
)
2006 struct predicate p
= true_predicate ();
2009 struct predicate op_non_const
;
2012 struct agg_position_info aggpos
;
2014 /* What statments might be optimized away
2015 when their arguments are constant
2016 TODO: also trivial builtins.
2017 builtin_constant_p is already handled later. */
2018 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2019 && gimple_code (stmt
) != GIMPLE_COND
2020 && gimple_code (stmt
) != GIMPLE_SWITCH
)
2023 /* Stores will stay anyway. */
2024 if (gimple_store_p (stmt
))
2027 is_load
= gimple_assign_load_p (stmt
);
2029 /* Loads can be optimized when the value is known. */
2033 gcc_assert (gimple_assign_single_p (stmt
));
2034 op
= gimple_assign_rhs1 (stmt
);
2035 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2042 /* See if we understand all operands before we start
2043 adding conditionals. */
2044 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2046 tree parm
= unmodified_parm (stmt
, use
);
2047 /* For arguments we can build a condition. */
2048 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2050 if (TREE_CODE (use
) != SSA_NAME
)
2052 /* If we know when operand is constant,
2053 we still can say something useful. */
2054 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2061 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2063 op_non_const
= false_predicate ();
2064 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2066 tree parm
= unmodified_parm (stmt
, use
);
2069 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2071 if (index
!= base_index
)
2072 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2077 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2078 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2080 if (gimple_code (stmt
) == GIMPLE_ASSIGN
2081 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
)
2082 nonconstant_names
[SSA_NAME_VERSION (gimple_assign_lhs (stmt
))]
2084 return op_non_const
;
2087 struct record_modified_bb_info
2093 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2094 set except for info->stmt. */
2097 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2099 struct record_modified_bb_info
*info
=
2100 (struct record_modified_bb_info
*) data
;
2101 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2103 bitmap_set_bit (info
->bb_set
,
2104 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2105 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2106 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2110 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2111 will change since last invocation of STMT.
2113 Value 0 is reserved for compile time invariants.
2114 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2115 ought to be REG_BR_PROB_BASE / estimated_iters. */
2118 param_change_prob (gimple stmt
, int i
)
2120 tree op
= gimple_call_arg (stmt
, i
);
2121 basic_block bb
= gimple_bb (stmt
);
2124 /* Global invariants neve change. */
2125 if (is_gimple_min_invariant (op
))
2127 /* We would have to do non-trivial analysis to really work out what
2128 is the probability of value to change (i.e. when init statement
2129 is in a sibling loop of the call).
2131 We do an conservative estimate: when call is executed N times more often
2132 than the statement defining value, we take the frequency 1/N. */
2133 if (TREE_CODE (op
) == SSA_NAME
)
2138 return REG_BR_PROB_BASE
;
2140 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2141 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2143 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2147 if (init_freq
< bb
->frequency
)
2148 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2150 return REG_BR_PROB_BASE
;
2153 base
= get_base_address (op
);
2158 struct record_modified_bb_info info
;
2161 tree init
= ctor_for_folding (base
);
2163 if (init
!= error_mark_node
)
2166 return REG_BR_PROB_BASE
;
2167 ao_ref_init (&refd
, op
);
2169 info
.bb_set
= BITMAP_ALLOC (NULL
);
2170 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2172 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2174 BITMAP_FREE (info
.bb_set
);
2175 return REG_BR_PROB_BASE
;
2178 /* Assume that every memory is initialized at entry.
2179 TODO: Can we easilly determine if value is always defined
2180 and thus we may skip entry block? */
2181 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2182 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2186 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2187 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2189 BITMAP_FREE (info
.bb_set
);
2190 if (max
< bb
->frequency
)
2191 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2193 return REG_BR_PROB_BASE
;
2195 return REG_BR_PROB_BASE
;
2198 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2199 sub-graph and if the predicate the condition depends on is known. If so,
2200 return true and store the pointer the predicate in *P. */
2203 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2204 struct inline_summary
*summary
, basic_block bb
,
2205 struct predicate
*p
,
2206 vec
<predicate_t
> nonconstant_names
)
2210 basic_block first_bb
= NULL
;
2213 if (single_pred_p (bb
))
2215 *p
= false_predicate ();
2219 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2221 if (single_succ_p (e
->src
))
2223 if (!single_pred_p (e
->src
))
2226 first_bb
= single_pred (e
->src
);
2227 else if (single_pred (e
->src
) != first_bb
)
2234 else if (e
->src
!= first_bb
)
2242 stmt
= last_stmt (first_bb
);
2244 || gimple_code (stmt
) != GIMPLE_COND
2245 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2248 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2249 gimple_cond_lhs (stmt
),
2251 if (true_predicate_p (p
))
2257 /* Given a PHI statement in a function described by inline properties SUMMARY
2258 and *P being the predicate describing whether the selected PHI argument is
2259 known, store a predicate for the result of the PHI statement into
2260 NONCONSTANT_NAMES, if possible. */
2263 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2264 struct predicate
*p
,
2265 vec
<predicate_t
> nonconstant_names
)
2269 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2271 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2272 if (!is_gimple_min_invariant (arg
))
2274 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2275 *p
= or_predicates (summary
->conds
, p
,
2276 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2277 if (true_predicate_p (p
))
2282 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2284 fprintf (dump_file
, "\t\tphi predicate: ");
2285 dump_predicate (dump_file
, summary
->conds
, p
);
2287 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2290 /* Return predicate specifying when array index in access OP becomes non-constant. */
2292 static struct predicate
2293 array_index_predicate (struct inline_summary
*info
,
2294 vec
< predicate_t
> nonconstant_names
, tree op
)
2296 struct predicate p
= false_predicate ();
2297 while (handled_component_p (op
))
2299 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2301 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2302 p
= or_predicates (info
->conds
, &p
,
2303 &nonconstant_names
[SSA_NAME_VERSION
2304 (TREE_OPERAND (op
, 1))]);
2306 op
= TREE_OPERAND (op
, 0);
2311 /* For a typical usage of __builtin_expect (a<b, 1), we
2312 may introduce an extra relation stmt:
2313 With the builtin, we have
2316 t3 = __builtin_expect (t2, 1);
2319 Without the builtin, we have
2322 This affects the size/time estimation and may have
2323 an impact on the earlier inlining.
2324 Here find this pattern and fix it up later. */
2327 find_foldable_builtin_expect (basic_block bb
)
2329 gimple_stmt_iterator bsi
;
2331 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2333 gimple stmt
= gsi_stmt (bsi
);
2334 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2335 || (is_gimple_call (stmt
)
2336 && gimple_call_internal_p (stmt
)
2337 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2339 tree var
= gimple_call_lhs (stmt
);
2340 tree arg
= gimple_call_arg (stmt
, 0);
2341 use_operand_p use_p
;
2348 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2350 while (TREE_CODE (arg
) == SSA_NAME
)
2352 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2353 if (!is_gimple_assign (stmt_tmp
))
2355 switch (gimple_assign_rhs_code (stmt_tmp
))
2374 arg
= gimple_assign_rhs1 (stmt_tmp
);
2377 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2378 && gimple_code (use_stmt
) == GIMPLE_COND
)
2385 /* Return true when the basic blocks contains only clobbers followed by RESX.
2386 Such BBs are kept around to make removal of dead stores possible with
2387 presence of EH and will be optimized out by optimize_clobbers later in the
2390 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2391 that can be clobber only, too.. When it is false, the RESX is not necessary
2392 on the end of basic block. */
2395 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2397 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2403 if (gsi_end_p (gsi
))
2405 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2409 else if (!single_succ_p (bb
))
2412 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2414 gimple stmt
= gsi_stmt (gsi
);
2415 if (is_gimple_debug (stmt
))
2417 if (gimple_clobber_p (stmt
))
2419 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2424 /* See if all predecestors are either throws or clobber only BBs. */
2425 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2426 if (!(e
->flags
& EDGE_EH
)
2427 && !clobber_only_eh_bb_p (e
->src
, false))
2433 /* Compute function body size parameters for NODE.
2434 When EARLY is true, we compute only simple summaries without
2435 non-trivial predicates to drive the early inliner. */
2438 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2441 /* Estimate static overhead for function prologue/epilogue and alignment. */
2443 /* Benefits are scaled by probability of elimination that is in range
2446 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2448 struct inline_summary
*info
= inline_summary (node
);
2449 struct predicate bb_predicate
;
2450 struct ipa_node_params
*parms_info
= NULL
;
2451 vec
<predicate_t
> nonconstant_names
= vNULL
;
2454 predicate array_index
= true_predicate ();
2455 gimple fix_builtin_expect_stmt
;
2460 if (optimize
&& !early
)
2462 calculate_dominance_info (CDI_DOMINATORS
);
2463 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2465 if (ipa_node_params_vector
.exists ())
2467 parms_info
= IPA_NODE_REF (node
);
2468 nonconstant_names
.safe_grow_cleared
2469 (SSANAMES (my_function
)->length ());
2474 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2477 /* When we run into maximal number of entries, we assign everything to the
2478 constant truth case. Be sure to have it in list. */
2479 bb_predicate
= true_predicate ();
2480 account_size_time (info
, 0, 0, &bb_predicate
);
2482 bb_predicate
= not_inlined_predicate ();
2483 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2485 gcc_assert (my_function
&& my_function
->cfg
);
2487 compute_bb_predicates (node
, parms_info
, info
);
2488 gcc_assert (cfun
== my_function
);
2489 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2490 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2491 for (n
= 0; n
< nblocks
; n
++)
2493 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2494 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2495 if (clobber_only_eh_bb_p (bb
))
2497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2498 fprintf (dump_file
, "\n Ignoring BB %i;"
2499 " it will be optimized away by cleanup_clobbers\n",
2504 /* TODO: Obviously predicates can be propagated down across CFG. */
2508 bb_predicate
= *(struct predicate
*) bb
->aux
;
2510 bb_predicate
= false_predicate ();
2513 bb_predicate
= true_predicate ();
2515 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2517 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2518 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2521 if (parms_info
&& nonconstant_names
.exists ())
2523 struct predicate phi_predicate
;
2524 bool first_phi
= true;
2526 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2530 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2537 fprintf (dump_file
, " ");
2538 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2540 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2545 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2547 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2550 gimple stmt
= gsi_stmt (bsi
);
2551 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2552 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2554 struct predicate will_be_nonconstant
;
2556 /* This relation stmt should be folded after we remove
2557 buildin_expect call. Adjust the cost here. */
2558 if (stmt
== fix_builtin_expect_stmt
)
2564 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2566 fprintf (dump_file
, " ");
2567 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2568 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2569 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2573 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2575 struct predicate this_array_index
;
2577 array_index_predicate (info
, nonconstant_names
,
2578 gimple_assign_rhs1 (stmt
));
2579 if (!false_predicate_p (&this_array_index
))
2581 and_predicates (info
->conds
, &array_index
,
2584 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2586 struct predicate this_array_index
;
2588 array_index_predicate (info
, nonconstant_names
,
2589 gimple_get_lhs (stmt
));
2590 if (!false_predicate_p (&this_array_index
))
2592 and_predicates (info
->conds
, &array_index
,
2597 if (is_gimple_call (stmt
)
2598 && !gimple_call_internal_p (stmt
))
2600 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2601 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2603 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2604 resolved as constant. We however don't want to optimize
2605 out the cgraph edges. */
2606 if (nonconstant_names
.exists ()
2607 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2608 && gimple_call_lhs (stmt
)
2609 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2611 struct predicate false_p
= false_predicate ();
2612 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2615 if (ipa_node_params_vector
.exists ())
2617 int count
= gimple_call_num_args (stmt
);
2621 es
->param
.safe_grow_cleared (count
);
2622 for (i
= 0; i
< count
; i
++)
2624 int prob
= param_change_prob (stmt
, i
);
2625 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2626 es
->param
[i
].change_prob
= prob
;
2630 es
->call_stmt_size
= this_size
;
2631 es
->call_stmt_time
= this_time
;
2632 es
->loop_depth
= bb_loop_depth (bb
);
2633 edge_set_predicate (edge
, &bb_predicate
);
2636 /* TODO: When conditional jump or swithc is known to be constant, but
2637 we did not translate it into the predicates, we really can account
2638 just maximum of the possible paths. */
2641 = will_be_nonconstant_predicate (parms_info
, info
,
2642 stmt
, nonconstant_names
);
2643 if (this_time
|| this_size
)
2649 prob
= eliminated_by_inlining_prob (stmt
);
2650 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2652 "\t\t50%% will be eliminated by inlining\n");
2653 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2654 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2657 p
= and_predicates (info
->conds
, &bb_predicate
,
2658 &will_be_nonconstant
);
2660 p
= true_predicate ();
2662 if (!false_predicate_p (&p
))
2666 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2667 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2670 /* We account everything but the calls. Calls have their own
2671 size/time info attached to cgraph edges. This is necessary
2672 in order to make the cost disappear after inlining. */
2673 if (!is_gimple_call (stmt
))
2677 struct predicate ip
= not_inlined_predicate ();
2678 ip
= and_predicates (info
->conds
, &ip
, &p
);
2679 account_size_time (info
, this_size
* prob
,
2680 this_time
* prob
, &ip
);
2683 account_size_time (info
, this_size
* (2 - prob
),
2684 this_time
* (2 - prob
), &p
);
2687 gcc_assert (time
>= 0);
2688 gcc_assert (size
>= 0);
2692 set_hint_predicate (&inline_summary (node
)->array_index
, array_index
);
2693 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2694 if (time
> MAX_TIME
)
2698 if (!early
&& nonconstant_names
.exists ())
2701 predicate loop_iterations
= true_predicate ();
2702 predicate loop_stride
= true_predicate ();
2704 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2705 flow_loops_dump (dump_file
, NULL
, 0);
2707 FOR_EACH_LOOP (loop
, 0)
2712 struct tree_niter_desc niter_desc
;
2713 basic_block
*body
= get_loop_body (loop
);
2714 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2716 exits
= get_loop_exit_edges (loop
);
2717 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2718 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2719 && !is_gimple_min_invariant (niter_desc
.niter
))
2721 predicate will_be_nonconstant
2722 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2725 if (!true_predicate_p (&will_be_nonconstant
))
2726 will_be_nonconstant
= and_predicates (info
->conds
,
2728 &will_be_nonconstant
);
2729 if (!true_predicate_p (&will_be_nonconstant
)
2730 && !false_predicate_p (&will_be_nonconstant
))
2731 /* This is slightly inprecise. We may want to represent each
2732 loop with independent predicate. */
2734 and_predicates (info
->conds
, &loop_iterations
,
2735 &will_be_nonconstant
);
2739 for (i
= 0; i
< loop
->num_nodes
; i
++)
2741 gimple_stmt_iterator gsi
;
2742 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2743 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2746 gimple stmt
= gsi_stmt (gsi
);
2751 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2753 predicate will_be_nonconstant
;
2756 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2757 || is_gimple_min_invariant (iv
.step
))
2760 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2763 if (!true_predicate_p (&will_be_nonconstant
))
2765 = and_predicates (info
->conds
,
2767 &will_be_nonconstant
);
2768 if (!true_predicate_p (&will_be_nonconstant
)
2769 && !false_predicate_p (&will_be_nonconstant
))
2770 /* This is slightly inprecise. We may want to represent
2771 each loop with independent predicate. */
2773 and_predicates (info
->conds
, &loop_stride
,
2774 &will_be_nonconstant
);
2780 set_hint_predicate (&inline_summary (node
)->loop_iterations
,
2782 set_hint_predicate (&inline_summary (node
)->loop_stride
, loop_stride
);
2785 FOR_ALL_BB_FN (bb
, my_function
)
2791 pool_free (edge_predicate_pool
, bb
->aux
);
2793 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2796 pool_free (edge_predicate_pool
, e
->aux
);
2800 inline_summary (node
)->self_time
= time
;
2801 inline_summary (node
)->self_size
= size
;
2802 nonconstant_names
.release ();
2803 if (optimize
&& !early
)
2805 loop_optimizer_finalize ();
2806 free_dominance_info (CDI_DOMINATORS
);
2810 fprintf (dump_file
, "\n");
2811 dump_inline_summary (dump_file
, node
);
2816 /* Compute parameters of functions used by inliner.
2817 EARLY is true when we compute parameters for the early inliner */
2820 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2822 HOST_WIDE_INT self_stack_size
;
2823 struct cgraph_edge
*e
;
2824 struct inline_summary
*info
;
2826 gcc_assert (!node
->global
.inlined_to
);
2828 inline_summary_alloc ();
2830 info
= inline_summary (node
);
2831 reset_inline_summary (node
);
2833 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2834 Once this happen, we will need to more curefully predict call
2836 if (node
->thunk
.thunk_p
)
2838 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2839 struct predicate t
= true_predicate ();
2841 info
->inlinable
= 0;
2842 node
->callees
->call_stmt_cannot_inline_p
= true;
2843 node
->local
.can_change_signature
= false;
2844 es
->call_stmt_time
= 1;
2845 es
->call_stmt_size
= 1;
2846 account_size_time (info
, 0, 0, &t
);
2850 /* Even is_gimple_min_invariant rely on current_function_decl. */
2851 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2853 /* Estimate the stack size for the function if we're optimizing. */
2854 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2855 info
->estimated_self_stack_size
= self_stack_size
;
2856 info
->estimated_stack_size
= self_stack_size
;
2857 info
->stack_frame_offset
= 0;
2859 /* Can this function be inlined at all? */
2860 if (!optimize
&& !lookup_attribute ("always_inline",
2861 DECL_ATTRIBUTES (node
->decl
)))
2862 info
->inlinable
= false;
2864 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2866 /* Type attributes can use parameter indices to describe them. */
2867 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2868 node
->local
.can_change_signature
= false;
2871 /* Otherwise, inlinable functions always can change signature. */
2872 if (info
->inlinable
)
2873 node
->local
.can_change_signature
= true;
2876 /* Functions calling builtin_apply can not change signature. */
2877 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2879 tree
cdecl = e
->callee
->decl
;
2880 if (DECL_BUILT_IN (cdecl)
2881 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2882 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2883 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2886 node
->local
.can_change_signature
= !e
;
2889 estimate_function_body_sizes (node
, early
);
2891 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2892 if (e
->callee
->comdat_local_p ())
2894 node
->calls_comdat_local
= (e
!= NULL
);
2896 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2897 info
->time
= info
->self_time
;
2898 info
->size
= info
->self_size
;
2899 info
->stack_frame_offset
= 0;
2900 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2901 #ifdef ENABLE_CHECKING
2902 inline_update_overall_summary (node
);
2903 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2910 /* Compute parameters of functions used by inliner using
2911 current_function_decl. */
2914 compute_inline_parameters_for_current (void)
2916 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2922 const pass_data pass_data_inline_parameters
=
2924 GIMPLE_PASS
, /* type */
2925 "inline_param", /* name */
2926 OPTGROUP_INLINE
, /* optinfo_flags */
2927 TV_INLINE_PARAMETERS
, /* tv_id */
2928 0, /* properties_required */
2929 0, /* properties_provided */
2930 0, /* properties_destroyed */
2931 0, /* todo_flags_start */
2932 0, /* todo_flags_finish */
2935 class pass_inline_parameters
: public gimple_opt_pass
2938 pass_inline_parameters (gcc::context
*ctxt
)
2939 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
2942 /* opt_pass methods: */
2943 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
2944 virtual unsigned int execute (function
*)
2946 return compute_inline_parameters_for_current ();
2949 }; // class pass_inline_parameters
2954 make_pass_inline_parameters (gcc::context
*ctxt
)
2956 return new pass_inline_parameters (ctxt
);
2960 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
2964 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
2965 int *size
, int *time
,
2966 vec
<tree
> known_vals
,
2967 vec
<tree
> known_binfos
,
2968 vec
<ipa_agg_jump_function_p
> known_aggs
)
2971 struct cgraph_node
*callee
;
2972 struct inline_summary
*isummary
;
2973 enum availability avail
;
2975 if (!known_vals
.exists () && !known_binfos
.exists ())
2977 if (!flag_indirect_inlining
)
2980 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_binfos
,
2985 /* Account for difference in cost between indirect and direct calls. */
2986 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
2987 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
2988 gcc_checking_assert (*time
>= 0);
2989 gcc_checking_assert (*size
>= 0);
2991 callee
= cgraph_node::get (target
);
2992 if (!callee
|| !callee
->definition
)
2994 callee
= callee
->function_symbol (&avail
);
2995 if (avail
< AVAIL_AVAILABLE
)
2997 isummary
= inline_summary (callee
);
2998 return isummary
->inlinable
;
3001 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3002 handle edge E with probability PROB.
3003 Set HINTS if edge may be devirtualized.
3004 KNOWN_VALS, KNOWN_AGGS and KNOWN_BINFOS describe context of the call
3008 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3011 vec
<tree
> known_vals
,
3012 vec
<tree
> known_binfos
,
3013 vec
<ipa_agg_jump_function_p
> known_aggs
,
3014 inline_hints
*hints
)
3016 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3017 int call_size
= es
->call_stmt_size
;
3018 int call_time
= es
->call_stmt_time
;
3021 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3022 known_vals
, known_binfos
, known_aggs
)
3023 && hints
&& e
->maybe_hot_p ())
3024 *hints
|= INLINE_HINT_indirect_call
;
3025 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3028 *min_size
+= cur_size
;
3029 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3030 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3031 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3032 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3037 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3039 POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_BINFOS describe context of
3043 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3044 int *min_size
, int *time
,
3045 inline_hints
*hints
,
3046 clause_t possible_truths
,
3047 vec
<tree
> known_vals
,
3048 vec
<tree
> known_binfos
,
3049 vec
<ipa_agg_jump_function_p
> known_aggs
)
3051 struct cgraph_edge
*e
;
3052 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3054 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3056 || evaluate_predicate (es
->predicate
, possible_truths
))
3058 if (e
->inline_failed
)
3060 /* Predicates of calls shall not use NOT_CHANGED codes,
3061 sowe do not need to compute probabilities. */
3062 estimate_edge_size_and_time (e
, size
,
3063 es
->predicate
? NULL
: min_size
,
3064 time
, REG_BR_PROB_BASE
,
3065 known_vals
, known_binfos
,
3069 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3072 known_vals
, known_binfos
,
3076 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3078 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3080 || evaluate_predicate (es
->predicate
, possible_truths
))
3081 estimate_edge_size_and_time (e
, size
,
3082 es
->predicate
? NULL
: min_size
,
3083 time
, REG_BR_PROB_BASE
,
3084 known_vals
, known_binfos
, known_aggs
,
3090 /* Estimate size and time needed to execute NODE assuming
3091 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_BINFOS
3092 information about NODE's arguments. If non-NULL use also probability
3093 information present in INLINE_PARAM_SUMMARY vector.
3094 Additionally detemine hints determined by the context. Finally compute
3095 minimal size needed for the call that is independent on the call context and
3096 can be used for fast estimates. Return the values in RET_SIZE,
3097 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3100 estimate_node_size_and_time (struct cgraph_node
*node
,
3101 clause_t possible_truths
,
3102 vec
<tree
> known_vals
,
3103 vec
<tree
> known_binfos
,
3104 vec
<ipa_agg_jump_function_p
> known_aggs
,
3105 int *ret_size
, int *ret_min_size
, int *ret_time
,
3106 inline_hints
*ret_hints
,
3107 vec
<inline_param_summary
>
3108 inline_param_summary
)
3110 struct inline_summary
*info
= inline_summary (node
);
3115 inline_hints hints
= 0;
3118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3121 fprintf (dump_file
, " Estimating body: %s/%i\n"
3122 " Known to be false: ", node
->name (),
3125 for (i
= predicate_not_inlined_condition
;
3126 i
< (predicate_first_dynamic_condition
3127 + (int) vec_safe_length (info
->conds
)); i
++)
3128 if (!(possible_truths
& (1 << i
)))
3131 fprintf (dump_file
, ", ");
3133 dump_condition (dump_file
, info
->conds
, i
);
3137 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3138 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3141 gcc_checking_assert (e
->time
>= 0);
3142 gcc_checking_assert (time
>= 0);
3143 if (!inline_param_summary
.exists ())
3147 int prob
= predicate_probability (info
->conds
,
3150 inline_param_summary
);
3151 gcc_checking_assert (prob
>= 0);
3152 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3153 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3155 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3156 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3157 gcc_checking_assert (time
>= 0);
3160 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3161 min_size
= (*info
->entry
)[0].size
;
3162 gcc_checking_assert (size
>= 0);
3163 gcc_checking_assert (time
>= 0);
3165 if (info
->loop_iterations
3166 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3167 hints
|= INLINE_HINT_loop_iterations
;
3168 if (info
->loop_stride
3169 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3170 hints
|= INLINE_HINT_loop_stride
;
3171 if (info
->array_index
3172 && !evaluate_predicate (info
->array_index
, possible_truths
))
3173 hints
|= INLINE_HINT_array_index
;
3175 hints
|= INLINE_HINT_in_scc
;
3176 if (DECL_DECLARED_INLINE_P (node
->decl
))
3177 hints
|= INLINE_HINT_declared_inline
;
3179 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3180 known_vals
, known_binfos
, known_aggs
);
3181 gcc_checking_assert (size
>= 0);
3182 gcc_checking_assert (time
>= 0);
3183 time
= RDIV (time
, INLINE_TIME_SCALE
);
3184 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3185 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3187 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3188 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3194 *ret_min_size
= min_size
;
3201 /* Estimate size and time needed to execute callee of EDGE assuming that
3202 parameters known to be constant at caller of EDGE are propagated.
3203 KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values
3204 and types for parameters. */
3207 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3208 vec
<tree
> known_vals
,
3209 vec
<tree
> known_binfos
,
3210 vec
<ipa_agg_jump_function_p
> known_aggs
,
3211 int *ret_size
, int *ret_time
,
3212 inline_hints
*hints
)
3216 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3218 estimate_node_size_and_time (node
, clause
, known_vals
, known_binfos
,
3219 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3222 /* Translate all conditions from callee representation into caller
3223 representation and symbolically evaluate predicate P into new predicate.
3225 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3226 is summary of function predicate P is from. OPERAND_MAP is array giving
3227 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3228 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3229 predicate under which callee is executed. OFFSET_MAP is an array of of
3230 offsets that need to be added to conditions, negative offset means that
3231 conditions relying on values passed by reference have to be discarded
3232 because they might not be preserved (and should be considered offset zero
3233 for other purposes). */
3235 static struct predicate
3236 remap_predicate (struct inline_summary
*info
,
3237 struct inline_summary
*callee_info
,
3238 struct predicate
*p
,
3239 vec
<int> operand_map
,
3240 vec
<int> offset_map
,
3241 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3244 struct predicate out
= true_predicate ();
3246 /* True predicate is easy. */
3247 if (true_predicate_p (p
))
3248 return *toplev_predicate
;
3249 for (i
= 0; p
->clause
[i
]; i
++)
3251 clause_t clause
= p
->clause
[i
];
3253 struct predicate clause_predicate
= false_predicate ();
3255 gcc_assert (i
< MAX_CLAUSES
);
3257 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3258 /* Do we have condition we can't disprove? */
3259 if (clause
& possible_truths
& (1 << cond
))
3261 struct predicate cond_predicate
;
3262 /* Work out if the condition can translate to predicate in the
3263 inlined function. */
3264 if (cond
>= predicate_first_dynamic_condition
)
3266 struct condition
*c
;
3268 c
= &(*callee_info
->conds
)[cond
3270 predicate_first_dynamic_condition
];
3271 /* See if we can remap condition operand to caller's operand.
3272 Otherwise give up. */
3273 if (!operand_map
.exists ()
3274 || (int) operand_map
.length () <= c
->operand_num
3275 || operand_map
[c
->operand_num
] == -1
3276 /* TODO: For non-aggregate conditions, adding an offset is
3277 basically an arithmetic jump function processing which
3278 we should support in future. */
3279 || ((!c
->agg_contents
|| !c
->by_ref
)
3280 && offset_map
[c
->operand_num
] > 0)
3281 || (c
->agg_contents
&& c
->by_ref
3282 && offset_map
[c
->operand_num
] < 0))
3283 cond_predicate
= true_predicate ();
3286 struct agg_position_info ap
;
3287 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3288 if (offset_delta
< 0)
3290 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3293 gcc_assert (!c
->agg_contents
3294 || c
->by_ref
|| offset_delta
== 0);
3295 ap
.offset
= c
->offset
+ offset_delta
;
3296 ap
.agg_contents
= c
->agg_contents
;
3297 ap
.by_ref
= c
->by_ref
;
3298 cond_predicate
= add_condition (info
,
3299 operand_map
[c
->operand_num
],
3300 &ap
, c
->code
, c
->val
);
3303 /* Fixed conditions remains same, construct single
3304 condition predicate. */
3307 cond_predicate
.clause
[0] = 1 << cond
;
3308 cond_predicate
.clause
[1] = 0;
3310 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3313 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3315 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3319 /* Update summary information of inline clones after inlining.
3320 Compute peak stack usage. */
3323 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3325 struct cgraph_edge
*e
;
3326 struct inline_summary
*callee_info
= inline_summary (node
);
3327 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
3330 callee_info
->stack_frame_offset
3331 = caller_info
->stack_frame_offset
3332 + caller_info
->estimated_self_stack_size
;
3333 peak
= callee_info
->stack_frame_offset
3334 + callee_info
->estimated_self_stack_size
;
3335 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3336 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3337 ipa_propagate_frequency (node
);
3338 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3340 if (!e
->inline_failed
)
3341 inline_update_callee_summaries (e
->callee
, depth
);
3342 inline_edge_summary (e
)->loop_depth
+= depth
;
3344 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3345 inline_edge_summary (e
)->loop_depth
+= depth
;
3348 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3349 When functoin A is inlined in B and A calls C with parameter that
3350 changes with probability PROB1 and C is known to be passthroug
3351 of argument if B that change with probability PROB2, the probability
3352 of change is now PROB1*PROB2. */
3355 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3356 struct cgraph_edge
*edge
)
3358 if (ipa_node_params_vector
.exists ())
3361 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3362 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3363 struct inline_edge_summary
*inlined_es
3364 = inline_edge_summary (inlined_edge
);
3366 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3368 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3369 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3370 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3371 < (int) inlined_es
->param
.length ()))
3373 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3374 int prob1
= es
->param
[i
].change_prob
;
3375 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3376 int prob
= combine_probabilities (prob1
, prob2
);
3378 if (prob1
&& prob2
&& !prob
)
3381 es
->param
[i
].change_prob
= prob
;
3387 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3389 Remap predicates of callees of NODE. Rest of arguments match
3392 Also update change probabilities. */
3395 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3396 struct cgraph_node
*node
,
3397 struct inline_summary
*info
,
3398 struct inline_summary
*callee_info
,
3399 vec
<int> operand_map
,
3400 vec
<int> offset_map
,
3401 clause_t possible_truths
,
3402 struct predicate
*toplev_predicate
)
3404 struct cgraph_edge
*e
;
3405 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3407 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3410 if (e
->inline_failed
)
3412 remap_edge_change_prob (inlined_edge
, e
);
3416 p
= remap_predicate (info
, callee_info
,
3417 es
->predicate
, operand_map
, offset_map
,
3418 possible_truths
, toplev_predicate
);
3419 edge_set_predicate (e
, &p
);
3420 /* TODO: We should remove the edge for code that will be
3421 optimized out, but we need to keep verifiers and tree-inline
3422 happy. Make it cold for now. */
3423 if (false_predicate_p (&p
))
3430 edge_set_predicate (e
, toplev_predicate
);
3433 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3434 operand_map
, offset_map
, possible_truths
,
3437 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3439 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3442 remap_edge_change_prob (inlined_edge
, e
);
3445 p
= remap_predicate (info
, callee_info
,
3446 es
->predicate
, operand_map
, offset_map
,
3447 possible_truths
, toplev_predicate
);
3448 edge_set_predicate (e
, &p
);
3449 /* TODO: We should remove the edge for code that will be optimized
3450 out, but we need to keep verifiers and tree-inline happy.
3451 Make it cold for now. */
3452 if (false_predicate_p (&p
))
3459 edge_set_predicate (e
, toplev_predicate
);
3463 /* Same as remap_predicate, but set result into hint *HINT. */
3466 remap_hint_predicate (struct inline_summary
*info
,
3467 struct inline_summary
*callee_info
,
3468 struct predicate
**hint
,
3469 vec
<int> operand_map
,
3470 vec
<int> offset_map
,
3471 clause_t possible_truths
,
3472 struct predicate
*toplev_predicate
)
3478 p
= remap_predicate (info
, callee_info
,
3480 operand_map
, offset_map
,
3481 possible_truths
, toplev_predicate
);
3482 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3485 set_hint_predicate (hint
, p
);
3487 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3491 /* We inlined EDGE. Update summary of the function we inlined into. */
3494 inline_merge_summary (struct cgraph_edge
*edge
)
3496 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
3497 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3498 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3499 struct inline_summary
*info
= inline_summary (to
);
3500 clause_t clause
= 0; /* not_inline is known to be false. */
3502 vec
<int> operand_map
= vNULL
;
3503 vec
<int> offset_map
= vNULL
;
3505 struct predicate toplev_predicate
;
3506 struct predicate true_p
= true_predicate ();
3507 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3510 toplev_predicate
= *es
->predicate
;
3512 toplev_predicate
= true_predicate ();
3514 if (ipa_node_params_vector
.exists () && callee_info
->conds
)
3516 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3517 int count
= ipa_get_cs_argument_count (args
);
3520 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3523 operand_map
.safe_grow_cleared (count
);
3524 offset_map
.safe_grow_cleared (count
);
3526 for (i
= 0; i
< count
; i
++)
3528 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3531 /* TODO: handle non-NOPs when merging. */
3532 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3534 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3535 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3536 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3539 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3541 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3542 if (offset
>= 0 && offset
< INT_MAX
)
3544 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3545 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3547 offset_map
[i
] = offset
;
3550 operand_map
[i
] = map
;
3551 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3554 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3556 struct predicate p
= remap_predicate (info
, callee_info
,
3557 &e
->predicate
, operand_map
,
3560 if (!false_predicate_p (&p
))
3562 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3563 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3564 int prob
= predicate_probability (callee_info
->conds
,
3567 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3568 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3569 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3570 if (prob
!= REG_BR_PROB_BASE
3571 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3573 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3574 (double) prob
/ REG_BR_PROB_BASE
);
3576 account_size_time (info
, e
->size
, add_time
, &p
);
3579 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3580 offset_map
, clause
, &toplev_predicate
);
3581 remap_hint_predicate (info
, callee_info
,
3582 &callee_info
->loop_iterations
,
3583 operand_map
, offset_map
, clause
, &toplev_predicate
);
3584 remap_hint_predicate (info
, callee_info
,
3585 &callee_info
->loop_stride
,
3586 operand_map
, offset_map
, clause
, &toplev_predicate
);
3587 remap_hint_predicate (info
, callee_info
,
3588 &callee_info
->array_index
,
3589 operand_map
, offset_map
, clause
, &toplev_predicate
);
3591 inline_update_callee_summaries (edge
->callee
,
3592 inline_edge_summary (edge
)->loop_depth
);
3594 /* We do not maintain predicates of inlined edges, free it. */
3595 edge_set_predicate (edge
, &true_p
);
3596 /* Similarly remove param summaries. */
3597 es
->param
.release ();
3598 operand_map
.release ();
3599 offset_map
.release ();
3602 /* For performance reasons inline_merge_summary is not updating overall size
3603 and time. Recompute it. */
3606 inline_update_overall_summary (struct cgraph_node
*node
)
3608 struct inline_summary
*info
= inline_summary (node
);
3614 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3616 info
->size
+= e
->size
, info
->time
+= e
->time
;
3617 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3618 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3620 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3622 ~(clause_t
) (1 << predicate_false_condition
),
3623 vNULL
, vNULL
, vNULL
);
3624 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3625 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3628 /* Return hints derrived from EDGE. */
3630 simple_edge_hints (struct cgraph_edge
*edge
)
3633 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3634 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3635 if (inline_summary (to
)->scc_no
3636 && inline_summary (to
)->scc_no
== inline_summary (edge
->callee
)->scc_no
3637 && !edge
->recursive_p ())
3638 hints
|= INLINE_HINT_same_scc
;
3640 if (to
->lto_file_data
&& edge
->callee
->lto_file_data
3641 && to
->lto_file_data
!= edge
->callee
->lto_file_data
)
3642 hints
|= INLINE_HINT_cross_module
;
3647 /* Estimate the time cost for the caller when inlining EDGE.
3648 Only to be called via estimate_edge_time, that handles the
3651 When caching, also update the cache entry. Compute both time and
3652 size, since we always need both metrics eventually. */
3655 do_estimate_edge_time (struct cgraph_edge
*edge
)
3660 struct cgraph_node
*callee
;
3662 vec
<tree
> known_vals
;
3663 vec
<tree
> known_binfos
;
3664 vec
<ipa_agg_jump_function_p
> known_aggs
;
3665 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3668 callee
= edge
->callee
->ultimate_alias_target ();
3670 gcc_checking_assert (edge
->inline_failed
);
3671 evaluate_properties_for_edge (edge
, true,
3672 &clause
, &known_vals
, &known_binfos
,
3674 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3675 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3677 /* When we have profile feedback, we can quite safely identify hot
3678 edges and for those we disable size limits. Don't do that when
3679 probability that caller will call the callee is low however, since it
3680 may hurt optimization of the caller's hot path. */
3681 if (edge
->count
&& edge
->maybe_hot_p ()
3683 > (edge
->caller
->global
.inlined_to
3684 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3685 hints
|= INLINE_HINT_known_hot
;
3687 known_vals
.release ();
3688 known_binfos
.release ();
3689 known_aggs
.release ();
3690 gcc_checking_assert (size
>= 0);
3691 gcc_checking_assert (time
>= 0);
3693 /* When caching, update the cache entry. */
3694 if (edge_growth_cache
.exists ())
3696 inline_summary (edge
->callee
)->min_size
= min_size
;
3697 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3698 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3699 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3701 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3702 hints
|= simple_edge_hints (edge
);
3703 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3709 /* Return estimated callee growth after inlining EDGE.
3710 Only to be called via estimate_edge_size. */
3713 do_estimate_edge_size (struct cgraph_edge
*edge
)
3716 struct cgraph_node
*callee
;
3718 vec
<tree
> known_vals
;
3719 vec
<tree
> known_binfos
;
3720 vec
<ipa_agg_jump_function_p
> known_aggs
;
3722 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3724 if (edge_growth_cache
.exists ())
3726 do_estimate_edge_time (edge
);
3727 size
= edge_growth_cache
[edge
->uid
].size
;
3728 gcc_checking_assert (size
);
3729 return size
- (size
> 0);
3732 callee
= edge
->callee
->ultimate_alias_target ();
3734 /* Early inliner runs without caching, go ahead and do the dirty work. */
3735 gcc_checking_assert (edge
->inline_failed
);
3736 evaluate_properties_for_edge (edge
, true,
3737 &clause
, &known_vals
, &known_binfos
,
3739 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3740 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3741 known_vals
.release ();
3742 known_binfos
.release ();
3743 known_aggs
.release ();
3748 /* Estimate the growth of the caller when inlining EDGE.
3749 Only to be called via estimate_edge_size. */
3752 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3755 struct cgraph_node
*callee
;
3757 vec
<tree
> known_vals
;
3758 vec
<tree
> known_binfos
;
3759 vec
<ipa_agg_jump_function_p
> known_aggs
;
3761 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3763 if (edge_growth_cache
.exists ())
3765 do_estimate_edge_time (edge
);
3766 hints
= edge_growth_cache
[edge
->uid
].hints
;
3767 gcc_checking_assert (hints
);
3771 callee
= edge
->callee
->ultimate_alias_target ();
3773 /* Early inliner runs without caching, go ahead and do the dirty work. */
3774 gcc_checking_assert (edge
->inline_failed
);
3775 evaluate_properties_for_edge (edge
, true,
3776 &clause
, &known_vals
, &known_binfos
,
3778 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
3779 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3780 known_vals
.release ();
3781 known_binfos
.release ();
3782 known_aggs
.release ();
3783 hints
|= simple_edge_hints (edge
);
3788 /* Estimate self time of the function NODE after inlining EDGE. */
3791 estimate_time_after_inlining (struct cgraph_node
*node
,
3792 struct cgraph_edge
*edge
)
3794 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3795 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3798 inline_summary (node
)->time
+ estimate_edge_time (edge
);
3801 if (time
> MAX_TIME
)
3805 return inline_summary (node
)->time
;
3809 /* Estimate the size of NODE after inlining EDGE which should be an
3810 edge to either NODE or a call inlined into NODE. */
3813 estimate_size_after_inlining (struct cgraph_node
*node
,
3814 struct cgraph_edge
*edge
)
3816 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3817 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3819 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
3820 gcc_assert (size
>= 0);
3823 return inline_summary (node
)->size
;
3829 struct cgraph_node
*node
;
3830 bool self_recursive
;
3835 /* Worker for do_estimate_growth. Collect growth for all callers. */
3838 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3840 struct cgraph_edge
*e
;
3841 struct growth_data
*d
= (struct growth_data
*) data
;
3843 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3845 gcc_checking_assert (e
->inline_failed
);
3847 if (e
->caller
== d
->node
3848 || (e
->caller
->global
.inlined_to
3849 && e
->caller
->global
.inlined_to
== d
->node
))
3850 d
->self_recursive
= true;
3851 d
->growth
+= estimate_edge_growth (e
);
3857 /* Estimate the growth caused by inlining NODE into all callees. */
3860 do_estimate_growth (struct cgraph_node
*node
)
3862 struct growth_data d
= { node
, 0, false };
3863 struct inline_summary
*info
= inline_summary (node
);
3865 node
->call_for_symbol_thunks_and_aliases (do_estimate_growth_1
, &d
, true);
3867 /* For self recursive functions the growth estimation really should be
3868 infinity. We don't want to return very large values because the growth
3869 plays various roles in badness computation fractions. Be sure to not
3870 return zero or negative growths. */
3871 if (d
.self_recursive
)
3872 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3873 else if (DECL_EXTERNAL (node
->decl
))
3877 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3878 d
.growth
-= info
->size
;
3879 /* COMDAT functions are very often not shared across multiple units
3880 since they come from various template instantiations.
3881 Take this into account. */
3882 else if (DECL_COMDAT (node
->decl
)
3883 && node
->can_remove_if_no_direct_calls_p ())
3884 d
.growth
-= (info
->size
3885 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3889 if (node_growth_cache
.exists ())
3891 if ((int) node_growth_cache
.length () <= node
->uid
)
3892 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
3893 node_growth_cache
[node
->uid
] = d
.growth
+ (d
.growth
>= 0);
3899 /* Make cheap estimation if growth of NODE is likely positive knowing
3900 EDGE_GROWTH of one particular edge.
3901 We assume that most of other edges will have similar growth
3902 and skip computation if there are too many callers. */
3905 growth_likely_positive (struct cgraph_node
*node
, int edge_growth ATTRIBUTE_UNUSED
)
3909 struct cgraph_edge
*e
;
3910 gcc_checking_assert (edge_growth
> 0);
3912 /* Unlike for functions called once, we play unsafe with
3913 COMDATs. We can allow that since we know functions
3914 in consideration are small (and thus risk is small) and
3915 moreover grow estimates already accounts that COMDAT
3916 functions may or may not disappear when eliminated from
3917 current unit. With good probability making aggressive
3918 choice in all units is going to make overall program
3921 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
3923 cgraph_will_be_removed_from_program_if_no_direct_calls */
3924 if (DECL_EXTERNAL (node
->decl
)
3925 || !node
->can_remove_if_no_direct_calls_p ())
3928 /* If there is cached value, just go ahead. */
3929 if ((int)node_growth_cache
.length () > node
->uid
3930 && (ret
= node_growth_cache
[node
->uid
]))
3932 if (!node
->will_be_removed_from_program_if_no_direct_calls_p ()
3933 && (!DECL_COMDAT (node
->decl
)
3934 || !node
->can_remove_if_no_direct_calls_p ()))
3936 max_callers
= inline_summary (node
)->size
* 4 / edge_growth
+ 2;
3938 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3944 return estimate_growth (node
) > 0;
3948 /* This function performs intraprocedural analysis in NODE that is required to
3949 inline indirect calls. */
3952 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
3954 ipa_analyze_node (node
);
3955 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3957 ipa_print_node_params (dump_file
, node
);
3958 ipa_print_node_jump_functions (dump_file
, node
);
3963 /* Note function body size. */
3966 inline_analyze_function (struct cgraph_node
*node
)
3968 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3971 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
3972 node
->name (), node
->order
);
3973 if (optimize
&& !node
->thunk
.thunk_p
)
3974 inline_indirect_intraprocedural_analysis (node
);
3975 compute_inline_parameters (node
, false);
3978 struct cgraph_edge
*e
;
3979 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3981 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
3982 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
3983 e
->call_stmt_cannot_inline_p
= true;
3985 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3987 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
3988 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
3989 e
->call_stmt_cannot_inline_p
= true;
3997 /* Called when new function is inserted to callgraph late. */
4000 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
4002 inline_analyze_function (node
);
4006 /* Note function body size. */
4009 inline_generate_summary (void)
4011 struct cgraph_node
*node
;
4013 /* When not optimizing, do not bother to analyze. Inlining is still done
4014 because edge redirection needs to happen there. */
4015 if (!optimize
&& !flag_lto
&& !flag_wpa
)
4018 function_insertion_hook_holder
=
4019 symtab
->add_cgraph_insertion_hook (&add_new_function
, NULL
);
4021 ipa_register_cgraph_hooks ();
4022 inline_free_summary ();
4024 FOR_EACH_DEFINED_FUNCTION (node
)
4026 inline_analyze_function (node
);
4030 /* Read predicate from IB. */
4032 static struct predicate
4033 read_predicate (struct lto_input_block
*ib
)
4035 struct predicate out
;
4041 gcc_assert (k
<= MAX_CLAUSES
);
4042 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4046 /* Zero-initialize the remaining clauses in OUT. */
4047 while (k
<= MAX_CLAUSES
)
4048 out
.clause
[k
++] = 0;
4054 /* Write inline summary for edge E to OB. */
4057 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4059 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4063 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4064 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4065 es
->loop_depth
= streamer_read_uhwi (ib
);
4066 p
= read_predicate (ib
);
4067 edge_set_predicate (e
, &p
);
4068 length
= streamer_read_uhwi (ib
);
4071 es
->param
.safe_grow_cleared (length
);
4072 for (i
= 0; i
< length
; i
++)
4073 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4078 /* Stream in inline summaries from the section. */
4081 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4084 const struct lto_function_header
*header
=
4085 (const struct lto_function_header
*) data
;
4086 const int cfg_offset
= sizeof (struct lto_function_header
);
4087 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4088 const int string_offset
= main_offset
+ header
->main_size
;
4089 struct data_in
*data_in
;
4090 unsigned int i
, count2
, j
;
4091 unsigned int f_count
;
4093 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
);
4096 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4097 header
->string_size
, vNULL
);
4098 f_count
= streamer_read_uhwi (&ib
);
4099 for (i
= 0; i
< f_count
; i
++)
4102 struct cgraph_node
*node
;
4103 struct inline_summary
*info
;
4104 lto_symtab_encoder_t encoder
;
4105 struct bitpack_d bp
;
4106 struct cgraph_edge
*e
;
4109 index
= streamer_read_uhwi (&ib
);
4110 encoder
= file_data
->symtab_node_encoder
;
4111 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4113 info
= inline_summary (node
);
4115 info
->estimated_stack_size
4116 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4117 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4118 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4120 bp
= streamer_read_bitpack (&ib
);
4121 info
->inlinable
= bp_unpack_value (&bp
, 1);
4123 count2
= streamer_read_uhwi (&ib
);
4124 gcc_assert (!info
->conds
);
4125 for (j
= 0; j
< count2
; j
++)
4128 c
.operand_num
= streamer_read_uhwi (&ib
);
4129 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4130 c
.val
= stream_read_tree (&ib
, data_in
);
4131 bp
= streamer_read_bitpack (&ib
);
4132 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4133 c
.by_ref
= bp_unpack_value (&bp
, 1);
4135 c
.offset
= streamer_read_uhwi (&ib
);
4136 vec_safe_push (info
->conds
, c
);
4138 count2
= streamer_read_uhwi (&ib
);
4139 gcc_assert (!info
->entry
);
4140 for (j
= 0; j
< count2
; j
++)
4142 struct size_time_entry e
;
4144 e
.size
= streamer_read_uhwi (&ib
);
4145 e
.time
= streamer_read_uhwi (&ib
);
4146 e
.predicate
= read_predicate (&ib
);
4148 vec_safe_push (info
->entry
, e
);
4151 p
= read_predicate (&ib
);
4152 set_hint_predicate (&info
->loop_iterations
, p
);
4153 p
= read_predicate (&ib
);
4154 set_hint_predicate (&info
->loop_stride
, p
);
4155 p
= read_predicate (&ib
);
4156 set_hint_predicate (&info
->array_index
, p
);
4157 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4158 read_inline_edge_summary (&ib
, e
);
4159 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4160 read_inline_edge_summary (&ib
, e
);
4163 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4165 lto_data_in_delete (data_in
);
4169 /* Read inline summary. Jump functions are shared among ipa-cp
4170 and inliner, so when ipa-cp is active, we don't need to write them
4174 inline_read_summary (void)
4176 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4177 struct lto_file_decl_data
*file_data
;
4180 inline_summary_alloc ();
4182 while ((file_data
= file_data_vec
[j
++]))
4185 const char *data
= lto_get_section_data (file_data
,
4186 LTO_section_inline_summary
,
4189 inline_read_section (file_data
, data
, len
);
4191 /* Fatal error here. We do not want to support compiling ltrans units
4192 with different version of compiler or different flags than the WPA
4193 unit, so this should never happen. */
4194 fatal_error ("ipa inline summary is missing in input file");
4198 ipa_register_cgraph_hooks ();
4200 ipa_prop_read_jump_functions ();
4202 function_insertion_hook_holder
=
4203 symtab
->add_cgraph_insertion_hook (&add_new_function
, NULL
);
4207 /* Write predicate P to OB. */
4210 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4214 for (j
= 0; p
->clause
[j
]; j
++)
4216 gcc_assert (j
< MAX_CLAUSES
);
4217 streamer_write_uhwi (ob
, p
->clause
[j
]);
4219 streamer_write_uhwi (ob
, 0);
4223 /* Write inline summary for edge E to OB. */
4226 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4228 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4231 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4232 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4233 streamer_write_uhwi (ob
, es
->loop_depth
);
4234 write_predicate (ob
, es
->predicate
);
4235 streamer_write_uhwi (ob
, es
->param
.length ());
4236 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4237 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4241 /* Write inline summary for node in SET.
4242 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4243 active, we don't need to write them twice. */
4246 inline_write_summary (void)
4248 struct cgraph_node
*node
;
4249 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4250 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4251 unsigned int count
= 0;
4254 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4256 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4257 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4258 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4261 streamer_write_uhwi (ob
, count
);
4263 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4265 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4266 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4267 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4269 struct inline_summary
*info
= inline_summary (node
);
4270 struct bitpack_d bp
;
4271 struct cgraph_edge
*edge
;
4274 struct condition
*c
;
4276 streamer_write_uhwi (ob
,
4277 lto_symtab_encoder_encode (encoder
,
4280 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4281 streamer_write_hwi (ob
, info
->self_size
);
4282 streamer_write_hwi (ob
, info
->self_time
);
4283 bp
= bitpack_create (ob
->main_stream
);
4284 bp_pack_value (&bp
, info
->inlinable
, 1);
4285 streamer_write_bitpack (&bp
);
4286 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4287 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4289 streamer_write_uhwi (ob
, c
->operand_num
);
4290 streamer_write_uhwi (ob
, c
->code
);
4291 stream_write_tree (ob
, c
->val
, true);
4292 bp
= bitpack_create (ob
->main_stream
);
4293 bp_pack_value (&bp
, c
->agg_contents
, 1);
4294 bp_pack_value (&bp
, c
->by_ref
, 1);
4295 streamer_write_bitpack (&bp
);
4296 if (c
->agg_contents
)
4297 streamer_write_uhwi (ob
, c
->offset
);
4299 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4300 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4302 streamer_write_uhwi (ob
, e
->size
);
4303 streamer_write_uhwi (ob
, e
->time
);
4304 write_predicate (ob
, &e
->predicate
);
4306 write_predicate (ob
, info
->loop_iterations
);
4307 write_predicate (ob
, info
->loop_stride
);
4308 write_predicate (ob
, info
->array_index
);
4309 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4310 write_inline_edge_summary (ob
, edge
);
4311 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4312 write_inline_edge_summary (ob
, edge
);
4315 streamer_write_char_stream (ob
->main_stream
, 0);
4316 produce_asm (ob
, NULL
);
4317 destroy_output_block (ob
);
4319 if (optimize
&& !flag_ipa_cp
)
4320 ipa_prop_write_jump_functions ();
4324 /* Release inline summary. */
4327 inline_free_summary (void)
4329 struct cgraph_node
*node
;
4330 if (!inline_edge_summary_vec
.exists ())
4332 FOR_EACH_DEFINED_FUNCTION (node
)
4334 reset_inline_summary (node
);
4335 if (function_insertion_hook_holder
)
4336 symtab
->remove_cgraph_insertion_hook (function_insertion_hook_holder
);
4337 function_insertion_hook_holder
= NULL
;
4338 if (node_removal_hook_holder
)
4339 symtab
->remove_cgraph_removal_hook (node_removal_hook_holder
);
4340 node_removal_hook_holder
= NULL
;
4341 if (edge_removal_hook_holder
)
4342 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4343 edge_removal_hook_holder
= NULL
;
4344 if (node_duplication_hook_holder
)
4345 symtab
->remove_cgraph_duplication_hook (node_duplication_hook_holder
);
4346 node_duplication_hook_holder
= NULL
;
4347 if (edge_duplication_hook_holder
)
4348 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4349 edge_duplication_hook_holder
= NULL
;
4350 vec_free (inline_summary_vec
);
4351 inline_edge_summary_vec
.release ();
4352 if (edge_predicate_pool
)
4353 free_alloc_pool (edge_predicate_pool
);
4354 edge_predicate_pool
= 0;