1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2015 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Analysis used by the inliner and other passes limiting code size growth.
23 We estimate for each function
25 - average function execution time
26 - inlining size benefit (that is how much of function body size
27 and its call sequence is expected to disappear by inlining)
28 - inlining time benefit
31 - call statement size and time
33 inlinie_summary datastructures store above information locally (i.e.
34 parameters of the function itself) and globally (i.e. parameters of
35 the function created by applying all the inline decisions already
36 present in the callgraph).
38 We provide accestor to the inline_summary datastructure and
39 basic logic updating the parameters when inlining is performed.
41 The summaries are context sensitive. Context means
42 1) partial assignment of known constant values of operands
43 2) whether function is inlined into the call or not.
44 It is easy to add more variants. To represent function size and time
45 that depends on context (i.e. it is known to be optimized away when
46 context is known either by inlining or from IP-CP and clonning),
47 we use predicates. Predicates are logical formulas in
48 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
49 specifying what conditions must be true. Conditions are simple test
50 of the form described above.
52 In order to make predicate (possibly) true, all of its clauses must
53 be (possibly) true. To make clause (possibly) true, one of conditions
54 it mentions must be (possibly) true. There are fixed bounds on
55 number of clauses and conditions and all the manipulation functions
56 are conservative in positive direction. I.e. we may lose precision
57 by thinking that predicate may be true even when it is not.
59 estimate_edge_size and estimate_edge_growth can be used to query
60 function size/time in the given context. inline_merge_summary merges
61 properties of caller and callee after inlining.
63 Finally pass_inline_parameters is exported. This is used to drive
64 computation of function parameters used by the early inliner. IPA
65 inlined performs analysis via its analyze_function method. */
69 #include "coretypes.h"
74 #include "double-int.h"
82 #include "fold-const.h"
83 #include "stor-layout.h"
84 #include "stringpool.h"
85 #include "print-tree.h"
86 #include "tree-inline.h"
87 #include "langhooks.h"
89 #include "diagnostic.h"
90 #include "gimple-pretty-print.h"
92 #include "tree-pass.h"
95 #include "hard-reg-set.h"
98 #include "dominance.h"
101 #include "basic-block.h"
102 #include "tree-ssa-alias.h"
103 #include "internal-fn.h"
104 #include "gimple-expr.h"
107 #include "gimple-iterator.h"
108 #include "gimple-ssa.h"
109 #include "tree-cfg.h"
110 #include "tree-phinodes.h"
111 #include "ssa-iterators.h"
112 #include "tree-ssanames.h"
113 #include "tree-ssa-loop-niter.h"
114 #include "tree-ssa-loop.h"
115 #include "hash-map.h"
116 #include "plugin-api.h"
119 #include "alloc-pool.h"
120 #include "symbol-summary.h"
121 #include "ipa-prop.h"
122 #include "lto-streamer.h"
123 #include "data-streamer.h"
124 #include "tree-streamer.h"
125 #include "ipa-inline.h"
127 #include "tree-scalar-evolution.h"
128 #include "ipa-utils.h"
130 #include "cfgexpand.h"
132 /* Estimate runtime of function can easilly run into huge numbers with many
133 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
134 integer. For anything larger we use gcov_type. */
135 #define MAX_TIME 500000
137 /* Number of bits in integer, but we really want to be stable across different
139 #define NUM_CONDITIONS 32
141 enum predicate_conditions
143 predicate_false_condition
= 0,
144 predicate_not_inlined_condition
= 1,
145 predicate_first_dynamic_condition
= 2
148 /* Special condition code we use to represent test that operand is compile time
150 #define IS_NOT_CONSTANT ERROR_MARK
151 /* Special condition code we use to represent test that operand is not changed
152 across invocation of the function. When operand IS_NOT_CONSTANT it is always
153 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
154 of executions even when they are not compile time constants. */
155 #define CHANGED IDENTIFIER_NODE
157 /* Holders of ipa cgraph hooks: */
158 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
159 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
160 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
161 static void inline_edge_duplication_hook (struct cgraph_edge
*,
162 struct cgraph_edge
*, void *);
164 /* VECtor holding inline summaries.
165 In GGC memory because conditions might point to constant trees. */
166 function_summary
<inline_summary
*> *inline_summaries
;
167 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
169 /* Cached node/edge growths. */
170 vec
<edge_growth_cache_entry
> edge_growth_cache
;
172 /* Edge predicates goes here. */
173 static alloc_pool edge_predicate_pool
;
175 /* Return true predicate (tautology).
176 We represent it by empty list of clauses. */
178 static inline struct predicate
179 true_predicate (void)
187 /* Return predicate testing single condition number COND. */
189 static inline struct predicate
190 single_cond_predicate (int cond
)
193 p
.clause
[0] = 1 << cond
;
199 /* Return false predicate. First clause require false condition. */
201 static inline struct predicate
202 false_predicate (void)
204 return single_cond_predicate (predicate_false_condition
);
208 /* Return true if P is (true). */
211 true_predicate_p (struct predicate
*p
)
213 return !p
->clause
[0];
217 /* Return true if P is (false). */
220 false_predicate_p (struct predicate
*p
)
222 if (p
->clause
[0] == (1 << predicate_false_condition
))
224 gcc_checking_assert (!p
->clause
[1]
225 && p
->clause
[0] == 1 << predicate_false_condition
);
232 /* Return predicate that is set true when function is not inlined. */
234 static inline struct predicate
235 not_inlined_predicate (void)
237 return single_cond_predicate (predicate_not_inlined_condition
);
240 /* Simple description of whether a memory load or a condition refers to a load
241 from an aggregate and if so, how and where from in the aggregate.
242 Individual fields have the same meaning like fields with the same name in
245 struct agg_position_info
247 HOST_WIDE_INT offset
;
252 /* Add condition to condition list CONDS. AGGPOS describes whether the used
253 oprand is loaded from an aggregate and where in the aggregate it is. It can
254 be NULL, which means this not a load from an aggregate. */
256 static struct predicate
257 add_condition (struct inline_summary
*summary
, int operand_num
,
258 struct agg_position_info
*aggpos
,
259 enum tree_code code
, tree val
)
263 struct condition new_cond
;
264 HOST_WIDE_INT offset
;
265 bool agg_contents
, by_ref
;
269 offset
= aggpos
->offset
;
270 agg_contents
= aggpos
->agg_contents
;
271 by_ref
= aggpos
->by_ref
;
276 agg_contents
= false;
280 gcc_checking_assert (operand_num
>= 0);
281 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
283 if (c
->operand_num
== operand_num
286 && c
->agg_contents
== agg_contents
287 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
288 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
290 /* Too many conditions. Give up and return constant true. */
291 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
292 return true_predicate ();
294 new_cond
.operand_num
= operand_num
;
295 new_cond
.code
= code
;
297 new_cond
.agg_contents
= agg_contents
;
298 new_cond
.by_ref
= by_ref
;
299 new_cond
.offset
= offset
;
300 vec_safe_push (summary
->conds
, new_cond
);
301 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
305 /* Add clause CLAUSE into the predicate P. */
308 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
312 int insert_here
= -1;
319 /* False clause makes the whole predicate false. Kill the other variants. */
320 if (clause
== (1 << predicate_false_condition
))
322 p
->clause
[0] = (1 << predicate_false_condition
);
326 if (false_predicate_p (p
))
329 /* No one should be silly enough to add false into nontrivial clauses. */
330 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
332 /* Look where to insert the clause. At the same time prune out
333 clauses of P that are implied by the new clause and thus
335 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
337 p
->clause
[i2
] = p
->clause
[i
];
342 /* If p->clause[i] implies clause, there is nothing to add. */
343 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
345 /* We had nothing to add, none of clauses should've become
347 gcc_checking_assert (i
== i2
);
351 if (p
->clause
[i
] < clause
&& insert_here
< 0)
354 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
355 Otherwise the p->clause[i] has to stay. */
356 if ((p
->clause
[i
] & clause
) != clause
)
360 /* Look for clauses that are obviously true. I.e.
361 op0 == 5 || op0 != 5. */
362 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
365 if (!(clause
& (1 << c1
)))
367 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
368 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
369 and thus there is no point for looking for them. */
370 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
372 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
373 if (clause
& (1 << c2
))
376 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
378 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
379 if (cc1
->operand_num
== cc2
->operand_num
380 && cc1
->val
== cc2
->val
381 && cc2
->code
!= IS_NOT_CONSTANT
382 && cc2
->code
!= CHANGED
383 && cc1
->code
== invert_tree_comparison (cc2
->code
,
384 HONOR_NANS (cc1
->val
)))
390 /* We run out of variants. Be conservative in positive direction. */
391 if (i2
== MAX_CLAUSES
)
393 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
394 p
->clause
[i2
+ 1] = 0;
395 if (insert_here
>= 0)
396 for (; i2
> insert_here
; i2
--)
397 p
->clause
[i2
] = p
->clause
[i2
- 1];
400 p
->clause
[insert_here
] = clause
;
406 static struct predicate
407 and_predicates (conditions conditions
,
408 struct predicate
*p
, struct predicate
*p2
)
410 struct predicate out
= *p
;
413 /* Avoid busy work. */
414 if (false_predicate_p (p2
) || true_predicate_p (p
))
416 if (false_predicate_p (p
) || true_predicate_p (p2
))
419 /* See how far predicates match. */
420 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
422 gcc_checking_assert (i
< MAX_CLAUSES
);
425 /* Combine the predicates rest. */
426 for (; p2
->clause
[i
]; i
++)
428 gcc_checking_assert (i
< MAX_CLAUSES
);
429 add_clause (conditions
, &out
, p2
->clause
[i
]);
435 /* Return true if predicates are obviously equal. */
438 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
441 for (i
= 0; p
->clause
[i
]; i
++)
443 gcc_checking_assert (i
< MAX_CLAUSES
);
444 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
445 gcc_checking_assert (!p2
->clause
[i
]
446 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
447 if (p
->clause
[i
] != p2
->clause
[i
])
450 return !p2
->clause
[i
];
456 static struct predicate
457 or_predicates (conditions conditions
,
458 struct predicate
*p
, struct predicate
*p2
)
460 struct predicate out
= true_predicate ();
463 /* Avoid busy work. */
464 if (false_predicate_p (p2
) || true_predicate_p (p
))
466 if (false_predicate_p (p
) || true_predicate_p (p2
))
468 if (predicates_equal_p (p
, p2
))
471 /* OK, combine the predicates. */
472 for (i
= 0; p
->clause
[i
]; i
++)
473 for (j
= 0; p2
->clause
[j
]; j
++)
475 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
476 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
482 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
483 if predicate P is known to be false. */
486 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
490 /* True remains true. */
491 if (true_predicate_p (p
))
494 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
496 /* See if we can find clause we can disprove. */
497 for (i
= 0; p
->clause
[i
]; i
++)
499 gcc_checking_assert (i
< MAX_CLAUSES
);
500 if (!(p
->clause
[i
] & possible_truths
))
506 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
507 instruction will be recomputed per invocation of the inlined call. */
510 predicate_probability (conditions conds
,
511 struct predicate
*p
, clause_t possible_truths
,
512 vec
<inline_param_summary
> inline_param_summary
)
515 int combined_prob
= REG_BR_PROB_BASE
;
517 /* True remains true. */
518 if (true_predicate_p (p
))
519 return REG_BR_PROB_BASE
;
521 if (false_predicate_p (p
))
524 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
526 /* See if we can find clause we can disprove. */
527 for (i
= 0; p
->clause
[i
]; i
++)
529 gcc_checking_assert (i
< MAX_CLAUSES
);
530 if (!(p
->clause
[i
] & possible_truths
))
536 if (!inline_param_summary
.exists ())
537 return REG_BR_PROB_BASE
;
538 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
539 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
541 if (i2
>= predicate_first_dynamic_condition
)
544 &(*conds
)[i2
- predicate_first_dynamic_condition
];
545 if (c
->code
== CHANGED
547 (int) inline_param_summary
.length ()))
550 inline_param_summary
[c
->operand_num
].change_prob
;
551 this_prob
= MAX (this_prob
, iprob
);
554 this_prob
= REG_BR_PROB_BASE
;
557 this_prob
= REG_BR_PROB_BASE
;
559 combined_prob
= MIN (this_prob
, combined_prob
);
564 return combined_prob
;
568 /* Dump conditional COND. */
571 dump_condition (FILE *f
, conditions conditions
, int cond
)
574 if (cond
== predicate_false_condition
)
575 fprintf (f
, "false");
576 else if (cond
== predicate_not_inlined_condition
)
577 fprintf (f
, "not inlined");
580 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
581 fprintf (f
, "op%i", c
->operand_num
);
583 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
584 c
->by_ref
? "ref " : "", c
->offset
);
585 if (c
->code
== IS_NOT_CONSTANT
)
587 fprintf (f
, " not constant");
590 if (c
->code
== CHANGED
)
592 fprintf (f
, " changed");
595 fprintf (f
, " %s ", op_symbol_code (c
->code
));
596 print_generic_expr (f
, c
->val
, 1);
601 /* Dump clause CLAUSE. */
604 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
611 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
612 if (clause
& (1 << i
))
617 dump_condition (f
, conds
, i
);
623 /* Dump predicate PREDICATE. */
626 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
629 if (true_predicate_p (pred
))
630 dump_clause (f
, conds
, 0);
632 for (i
= 0; pred
->clause
[i
]; i
++)
636 dump_clause (f
, conds
, pred
->clause
[i
]);
642 /* Dump inline hints. */
644 dump_inline_hints (FILE *f
, inline_hints hints
)
648 fprintf (f
, "inline hints:");
649 if (hints
& INLINE_HINT_indirect_call
)
651 hints
&= ~INLINE_HINT_indirect_call
;
652 fprintf (f
, " indirect_call");
654 if (hints
& INLINE_HINT_loop_iterations
)
656 hints
&= ~INLINE_HINT_loop_iterations
;
657 fprintf (f
, " loop_iterations");
659 if (hints
& INLINE_HINT_loop_stride
)
661 hints
&= ~INLINE_HINT_loop_stride
;
662 fprintf (f
, " loop_stride");
664 if (hints
& INLINE_HINT_same_scc
)
666 hints
&= ~INLINE_HINT_same_scc
;
667 fprintf (f
, " same_scc");
669 if (hints
& INLINE_HINT_in_scc
)
671 hints
&= ~INLINE_HINT_in_scc
;
672 fprintf (f
, " in_scc");
674 if (hints
& INLINE_HINT_cross_module
)
676 hints
&= ~INLINE_HINT_cross_module
;
677 fprintf (f
, " cross_module");
679 if (hints
& INLINE_HINT_declared_inline
)
681 hints
&= ~INLINE_HINT_declared_inline
;
682 fprintf (f
, " declared_inline");
684 if (hints
& INLINE_HINT_array_index
)
686 hints
&= ~INLINE_HINT_array_index
;
687 fprintf (f
, " array_index");
689 if (hints
& INLINE_HINT_known_hot
)
691 hints
&= ~INLINE_HINT_known_hot
;
692 fprintf (f
, " known_hot");
698 /* Record SIZE and TIME under condition PRED into the inline summary. */
701 account_size_time (struct inline_summary
*summary
, int size
, int time
,
702 struct predicate
*pred
)
708 if (false_predicate_p (pred
))
711 /* We need to create initial empty unconitional clause, but otherwie
712 we don't need to account empty times and sizes. */
713 if (!size
&& !time
&& summary
->entry
)
716 /* Watch overflow that might result from insane profiles. */
717 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
718 time
= MAX_TIME
* INLINE_TIME_SCALE
;
719 gcc_assert (time
>= 0);
721 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
722 if (predicates_equal_p (&e
->predicate
, pred
))
731 e
= &(*summary
->entry
)[0];
732 gcc_assert (!e
->predicate
.clause
[0]);
733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
735 "\t\tReached limit on number of entries, "
736 "ignoring the predicate.");
738 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
741 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
742 ((double) size
) / INLINE_SIZE_SCALE
,
743 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
744 dump_predicate (dump_file
, summary
->conds
, pred
);
748 struct size_time_entry new_entry
;
749 new_entry
.size
= size
;
750 new_entry
.time
= time
;
751 new_entry
.predicate
= *pred
;
752 vec_safe_push (summary
->entry
, new_entry
);
758 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
759 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
763 /* Set predicate for edge E. */
766 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
768 struct inline_edge_summary
*es
= inline_edge_summary (e
);
770 /* If the edge is determined to be never executed, redirect it
771 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
772 if (predicate
&& false_predicate_p (predicate
) && e
->callee
)
774 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
776 e
->redirect_callee (cgraph_node::get_create
777 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
)));
778 e
->inline_failed
= CIF_UNREACHABLE
;
779 es
->call_stmt_size
= 0;
780 es
->call_stmt_time
= 0;
782 callee
->remove_symbol_and_inline_clones ();
784 if (predicate
&& !true_predicate_p (predicate
))
787 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
788 *es
->predicate
= *predicate
;
793 pool_free (edge_predicate_pool
, es
->predicate
);
794 es
->predicate
= NULL
;
798 /* Set predicate for hint *P. */
801 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
803 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
806 pool_free (edge_predicate_pool
, *p
);
812 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
818 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
819 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
820 Return clause of possible truths. When INLINE_P is true, assume that we are
823 ERROR_MARK means compile time invariant. */
826 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
828 vec
<tree
> known_vals
,
829 vec
<ipa_agg_jump_function_p
>
832 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
833 struct inline_summary
*info
= inline_summaries
->get (node
);
837 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
842 /* We allow call stmt to have fewer arguments than the callee function
843 (especially for K&R style programs). So bound check here (we assume
844 known_aggs vector, if non-NULL, has the same length as
846 gcc_checking_assert (!known_aggs
.exists ()
847 || (known_vals
.length () == known_aggs
.length ()));
848 if (c
->operand_num
>= (int) known_vals
.length ())
850 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
856 struct ipa_agg_jump_function
*agg
;
858 if (c
->code
== CHANGED
860 && (known_vals
[c
->operand_num
] == error_mark_node
))
863 if (known_aggs
.exists ())
865 agg
= known_aggs
[c
->operand_num
];
866 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
873 val
= known_vals
[c
->operand_num
];
874 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
880 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
883 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
886 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
887 TYPE_SIZE (TREE_TYPE (val
)), 0))
889 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
892 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
895 if (res
&& integer_zerop (res
))
898 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
904 /* Work out what conditions might be true at invocation of E. */
907 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
908 clause_t
*clause_ptr
,
909 vec
<tree
> *known_vals_ptr
,
910 vec
<ipa_polymorphic_call_context
>
912 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
914 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
915 struct inline_summary
*info
= inline_summaries
->get (callee
);
916 vec
<tree
> known_vals
= vNULL
;
917 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
920 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
922 known_vals_ptr
->create (0);
923 if (known_contexts_ptr
)
924 known_contexts_ptr
->create (0);
926 if (ipa_node_params_sum
927 && !e
->call_stmt_cannot_inline_p
928 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
930 struct ipa_node_params
*parms_info
;
931 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
932 struct inline_edge_summary
*es
= inline_edge_summary (e
);
933 int i
, count
= ipa_get_cs_argument_count (args
);
935 if (e
->caller
->global
.inlined_to
)
936 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
938 parms_info
= IPA_NODE_REF (e
->caller
);
940 if (count
&& (info
->conds
|| known_vals_ptr
))
941 known_vals
.safe_grow_cleared (count
);
942 if (count
&& (info
->conds
|| known_aggs_ptr
))
943 known_aggs
.safe_grow_cleared (count
);
944 if (count
&& known_contexts_ptr
)
945 known_contexts_ptr
->safe_grow_cleared (count
);
947 for (i
= 0; i
< count
; i
++)
949 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
950 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
952 if (!cst
&& e
->call_stmt
953 && i
< (int)gimple_call_num_args (e
->call_stmt
))
955 cst
= gimple_call_arg (e
->call_stmt
, i
);
956 if (!is_gimple_min_invariant (cst
))
961 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
962 if (known_vals
.exists ())
965 else if (inline_p
&& !es
->param
[i
].change_prob
)
966 known_vals
[i
] = error_mark_node
;
968 if (known_contexts_ptr
)
969 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
971 /* TODO: When IPA-CP starts propagating and merging aggregate jump
972 functions, use its knowledge of the caller too, just like the
973 scalar case above. */
974 known_aggs
[i
] = &jf
->agg
;
977 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
978 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
980 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
982 if (count
&& (info
->conds
|| known_vals_ptr
))
983 known_vals
.safe_grow_cleared (count
);
984 for (i
= 0; i
< count
; i
++)
986 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
987 if (!is_gimple_min_invariant (cst
))
995 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
996 known_vals
, known_aggs
);
999 *known_vals_ptr
= known_vals
;
1001 known_vals
.release ();
1004 *known_aggs_ptr
= known_aggs
;
1006 known_aggs
.release ();
1010 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
1013 inline_summary_alloc (void)
1015 if (!edge_removal_hook_holder
)
1016 edge_removal_hook_holder
=
1017 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1018 if (!edge_duplication_hook_holder
)
1019 edge_duplication_hook_holder
=
1020 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1022 if (!inline_summaries
)
1023 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1025 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1026 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1027 if (!edge_predicate_pool
)
1028 edge_predicate_pool
= create_alloc_pool ("edge predicates",
1029 sizeof (struct predicate
), 10);
1032 /* We are called multiple time for given function; clear
1033 data from previous run so they are not cumulated. */
1036 reset_inline_edge_summary (struct cgraph_edge
*e
)
1038 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1040 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1042 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1044 pool_free (edge_predicate_pool
, es
->predicate
);
1045 es
->predicate
= NULL
;
1046 es
->param
.release ();
1050 /* We are called multiple time for given function; clear
1051 data from previous run so they are not cumulated. */
1054 reset_inline_summary (struct cgraph_node
*node
,
1055 inline_summary
*info
)
1057 struct cgraph_edge
*e
;
1059 info
->self_size
= info
->self_time
= 0;
1060 info
->estimated_stack_size
= 0;
1061 info
->estimated_self_stack_size
= 0;
1062 info
->stack_frame_offset
= 0;
1067 if (info
->loop_iterations
)
1069 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1070 info
->loop_iterations
= NULL
;
1072 if (info
->loop_stride
)
1074 pool_free (edge_predicate_pool
, info
->loop_stride
);
1075 info
->loop_stride
= NULL
;
1077 if (info
->array_index
)
1079 pool_free (edge_predicate_pool
, info
->array_index
);
1080 info
->array_index
= NULL
;
1082 vec_free (info
->conds
);
1083 vec_free (info
->entry
);
1084 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1085 reset_inline_edge_summary (e
);
1086 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1087 reset_inline_edge_summary (e
);
1090 /* Hook that is called by cgraph.c when a node is removed. */
1093 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1095 reset_inline_summary (node
, info
);
1098 /* Remap predicate P of former function to be predicate of duplicated function.
1099 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1100 INFO is inline summary of the duplicated node. */
1102 static struct predicate
1103 remap_predicate_after_duplication (struct predicate
*p
,
1104 clause_t possible_truths
,
1105 struct inline_summary
*info
)
1107 struct predicate new_predicate
= true_predicate ();
1109 for (j
= 0; p
->clause
[j
]; j
++)
1110 if (!(possible_truths
& p
->clause
[j
]))
1112 new_predicate
= false_predicate ();
1116 add_clause (info
->conds
, &new_predicate
,
1117 possible_truths
& p
->clause
[j
]);
1118 return new_predicate
;
1121 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1122 Additionally care about allocating new memory slot for updated predicate
1123 and set it to NULL when it becomes true or false (and thus uninteresting).
1127 remap_hint_predicate_after_duplication (struct predicate
**p
,
1128 clause_t possible_truths
,
1129 struct inline_summary
*info
)
1131 struct predicate new_predicate
;
1136 new_predicate
= remap_predicate_after_duplication (*p
,
1137 possible_truths
, info
);
1138 /* We do not want to free previous predicate; it is used by node origin. */
1140 set_hint_predicate (p
, new_predicate
);
1144 /* Hook that is called by cgraph.c when a node is duplicated. */
1146 inline_summary_t::duplicate (cgraph_node
*src
,
1149 inline_summary
*info
)
1151 inline_summary_alloc ();
1152 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1153 /* TODO: as an optimization, we may avoid copying conditions
1154 that are known to be false or true. */
1155 info
->conds
= vec_safe_copy (info
->conds
);
1157 /* When there are any replacements in the function body, see if we can figure
1158 out that something was optimized out. */
1159 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1161 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1162 /* Use SRC parm info since it may not be copied yet. */
1163 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1164 vec
<tree
> known_vals
= vNULL
;
1165 int count
= ipa_get_param_count (parms_info
);
1167 clause_t possible_truths
;
1168 struct predicate true_pred
= true_predicate ();
1170 int optimized_out_size
= 0;
1171 bool inlined_to_p
= false;
1172 struct cgraph_edge
*edge
;
1175 known_vals
.safe_grow_cleared (count
);
1176 for (i
= 0; i
< count
; i
++)
1178 struct ipa_replace_map
*r
;
1180 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1182 if (((!r
->old_tree
&& r
->parm_num
== i
)
1183 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1184 && r
->replace_p
&& !r
->ref_p
)
1186 known_vals
[i
] = r
->new_tree
;
1191 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1194 known_vals
.release ();
1196 account_size_time (info
, 0, 0, &true_pred
);
1198 /* Remap size_time vectors.
1199 Simplify the predicate by prunning out alternatives that are known
1201 TODO: as on optimization, we can also eliminate conditions known
1203 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1205 struct predicate new_predicate
;
1206 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1209 if (false_predicate_p (&new_predicate
))
1210 optimized_out_size
+= e
->size
;
1212 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1215 /* Remap edge predicates with the same simplification as above.
1216 Also copy constantness arrays. */
1217 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1219 struct predicate new_predicate
;
1220 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1222 if (!edge
->inline_failed
)
1223 inlined_to_p
= true;
1226 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1229 if (false_predicate_p (&new_predicate
)
1230 && !false_predicate_p (es
->predicate
))
1232 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1233 edge
->frequency
= 0;
1235 edge_set_predicate (edge
, &new_predicate
);
1238 /* Remap indirect edge predicates with the same simplificaiton as above.
1239 Also copy constantness arrays. */
1240 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1242 struct predicate new_predicate
;
1243 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1245 gcc_checking_assert (edge
->inline_failed
);
1248 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1251 if (false_predicate_p (&new_predicate
)
1252 && !false_predicate_p (es
->predicate
))
1254 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1255 edge
->frequency
= 0;
1257 edge_set_predicate (edge
, &new_predicate
);
1259 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1260 possible_truths
, info
);
1261 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1262 possible_truths
, info
);
1263 remap_hint_predicate_after_duplication (&info
->array_index
,
1264 possible_truths
, info
);
1266 /* If inliner or someone after inliner will ever start producing
1267 non-trivial clones, we will get trouble with lack of information
1268 about updating self sizes, because size vectors already contains
1269 sizes of the calees. */
1270 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1274 info
->entry
= vec_safe_copy (info
->entry
);
1275 if (info
->loop_iterations
)
1277 predicate p
= *info
->loop_iterations
;
1278 info
->loop_iterations
= NULL
;
1279 set_hint_predicate (&info
->loop_iterations
, p
);
1281 if (info
->loop_stride
)
1283 predicate p
= *info
->loop_stride
;
1284 info
->loop_stride
= NULL
;
1285 set_hint_predicate (&info
->loop_stride
, p
);
1287 if (info
->array_index
)
1289 predicate p
= *info
->array_index
;
1290 info
->array_index
= NULL
;
1291 set_hint_predicate (&info
->array_index
, p
);
1294 inline_update_overall_summary (dst
);
1298 /* Hook that is called by cgraph.c when a node is duplicated. */
1301 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1302 struct cgraph_edge
*dst
,
1303 ATTRIBUTE_UNUSED
void *data
)
1305 struct inline_edge_summary
*info
;
1306 struct inline_edge_summary
*srcinfo
;
1307 inline_summary_alloc ();
1308 info
= inline_edge_summary (dst
);
1309 srcinfo
= inline_edge_summary (src
);
1310 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1311 info
->predicate
= NULL
;
1312 edge_set_predicate (dst
, srcinfo
->predicate
);
1313 info
->param
= srcinfo
->param
.copy ();
1314 if (!dst
->indirect_unknown_callee
&& src
->indirect_unknown_callee
)
1316 info
->call_stmt_size
-= (eni_size_weights
.indirect_call_cost
1317 - eni_size_weights
.call_cost
);
1318 info
->call_stmt_time
-= (eni_time_weights
.indirect_call_cost
1319 - eni_time_weights
.call_cost
);
1324 /* Keep edge cache consistent across edge removal. */
1327 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1328 void *data ATTRIBUTE_UNUSED
)
1330 if (edge_growth_cache
.exists ())
1331 reset_edge_growth_cache (edge
);
1332 reset_inline_edge_summary (edge
);
1336 /* Initialize growth caches. */
1339 initialize_growth_caches (void)
1341 if (symtab
->edges_max_uid
)
1342 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1346 /* Free growth caches. */
1349 free_growth_caches (void)
1351 edge_growth_cache
.release ();
1355 /* Dump edge summaries associated to NODE and recursively to all clones.
1356 Indent by INDENT. */
1359 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1360 struct inline_summary
*info
)
1362 struct cgraph_edge
*edge
;
1363 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1365 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1366 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1370 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1371 " time: %2i callee size:%2i stack:%2i",
1372 indent
, "", callee
->name (), callee
->order
,
1373 !edge
->inline_failed
1374 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1375 indent
, "", es
->loop_depth
, edge
->frequency
,
1376 es
->call_stmt_size
, es
->call_stmt_time
,
1377 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1378 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1382 fprintf (f
, " predicate: ");
1383 dump_predicate (f
, info
->conds
, es
->predicate
);
1387 if (es
->param
.exists ())
1388 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1390 int prob
= es
->param
[i
].change_prob
;
1393 fprintf (f
, "%*s op%i is compile time invariant\n",
1395 else if (prob
!= REG_BR_PROB_BASE
)
1396 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1397 prob
* 100.0 / REG_BR_PROB_BASE
);
1399 if (!edge
->inline_failed
)
1401 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1402 " callee size %i\n",
1404 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1405 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1406 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1407 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1410 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1412 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1413 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1417 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1420 fprintf (f
, "predicate: ");
1421 dump_predicate (f
, info
->conds
, es
->predicate
);
1430 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1432 if (node
->definition
)
1434 struct inline_summary
*s
= inline_summaries
->get (node
);
1437 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1439 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1440 fprintf (f
, " always_inline");
1442 fprintf (f
, " inlinable");
1443 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1444 fprintf (f
, " global time: %i\n", s
->time
);
1445 fprintf (f
, " self size: %i\n", s
->self_size
);
1446 fprintf (f
, " global size: %i\n", s
->size
);
1447 fprintf (f
, " min size: %i\n", s
->min_size
);
1448 fprintf (f
, " self stack: %i\n",
1449 (int) s
->estimated_self_stack_size
);
1450 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1452 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1454 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1455 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1457 fprintf (f
, " size:%f, time:%f, predicate:",
1458 (double) e
->size
/ INLINE_SIZE_SCALE
,
1459 (double) e
->time
/ INLINE_TIME_SCALE
);
1460 dump_predicate (f
, s
->conds
, &e
->predicate
);
1462 if (s
->loop_iterations
)
1464 fprintf (f
, " loop iterations:");
1465 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1469 fprintf (f
, " loop stride:");
1470 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1474 fprintf (f
, " array index:");
1475 dump_predicate (f
, s
->conds
, s
->array_index
);
1477 fprintf (f
, " calls:\n");
1478 dump_inline_edge_summary (f
, 4, node
, s
);
1484 debug_inline_summary (struct cgraph_node
*node
)
1486 dump_inline_summary (stderr
, node
);
1490 dump_inline_summaries (FILE *f
)
1492 struct cgraph_node
*node
;
1494 FOR_EACH_DEFINED_FUNCTION (node
)
1495 if (!node
->global
.inlined_to
)
1496 dump_inline_summary (f
, node
);
1499 /* Give initial reasons why inlining would fail on EDGE. This gets either
1500 nullified or usually overwritten by more precise reasons later. */
1503 initialize_inline_failed (struct cgraph_edge
*e
)
1505 struct cgraph_node
*callee
= e
->callee
;
1507 if (e
->indirect_unknown_callee
)
1508 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1509 else if (!callee
->definition
)
1510 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1511 else if (callee
->local
.redefined_extern_inline
)
1512 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1513 else if (e
->call_stmt_cannot_inline_p
)
1514 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1515 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1516 /* We can't inline if the function is spawing a function. */
1517 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1519 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1522 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1523 boolean variable pointed to by DATA. */
1526 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1529 bool *b
= (bool *) data
;
1534 /* If OP refers to value of function parameter, return the corresponding
1538 unmodified_parm_1 (gimple stmt
, tree op
)
1540 /* SSA_NAME referring to parm default def? */
1541 if (TREE_CODE (op
) == SSA_NAME
1542 && SSA_NAME_IS_DEFAULT_DEF (op
)
1543 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1544 return SSA_NAME_VAR (op
);
1545 /* Non-SSA parm reference? */
1546 if (TREE_CODE (op
) == PARM_DECL
)
1548 bool modified
= false;
1551 ao_ref_init (&refd
, op
);
1552 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1560 /* If OP refers to value of function parameter, return the corresponding
1561 parameter. Also traverse chains of SSA register assignments. */
1564 unmodified_parm (gimple stmt
, tree op
)
1566 tree res
= unmodified_parm_1 (stmt
, op
);
1570 if (TREE_CODE (op
) == SSA_NAME
1571 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1572 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1573 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1574 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1578 /* If OP refers to a value of a function parameter or value loaded from an
1579 aggregate passed to a parameter (either by value or reference), return TRUE
1580 and store the number of the parameter to *INDEX_P and information whether
1581 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1582 the function parameters, STMT is the statement in which OP is used or
1586 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1587 gimple stmt
, tree op
, int *index_p
,
1588 struct agg_position_info
*aggpos
)
1590 tree res
= unmodified_parm_1 (stmt
, op
);
1592 gcc_checking_assert (aggpos
);
1595 *index_p
= ipa_get_param_decl_index (info
, res
);
1598 aggpos
->agg_contents
= false;
1599 aggpos
->by_ref
= false;
1603 if (TREE_CODE (op
) == SSA_NAME
)
1605 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1606 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1608 stmt
= SSA_NAME_DEF_STMT (op
);
1609 op
= gimple_assign_rhs1 (stmt
);
1610 if (!REFERENCE_CLASS_P (op
))
1611 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1615 aggpos
->agg_contents
= true;
1616 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1620 /* See if statement might disappear after inlining.
1621 0 - means not eliminated
1622 1 - half of statements goes away
1623 2 - for sure it is eliminated.
1624 We are not terribly sophisticated, basically looking for simple abstraction
1625 penalty wrappers. */
1628 eliminated_by_inlining_prob (gimple stmt
)
1630 enum gimple_code code
= gimple_code (stmt
);
1631 enum tree_code rhs_code
;
1641 if (gimple_num_ops (stmt
) != 2)
1644 rhs_code
= gimple_assign_rhs_code (stmt
);
1646 /* Casts of parameters, loads from parameters passed by reference
1647 and stores to return value or parameters are often free after
1648 inlining dua to SRA and further combining.
1649 Assume that half of statements goes away. */
1650 if (CONVERT_EXPR_CODE_P (rhs_code
)
1651 || rhs_code
== VIEW_CONVERT_EXPR
1652 || rhs_code
== ADDR_EXPR
1653 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1655 tree rhs
= gimple_assign_rhs1 (stmt
);
1656 tree lhs
= gimple_assign_lhs (stmt
);
1657 tree inner_rhs
= get_base_address (rhs
);
1658 tree inner_lhs
= get_base_address (lhs
);
1659 bool rhs_free
= false;
1660 bool lhs_free
= false;
1667 /* Reads of parameter are expected to be free. */
1668 if (unmodified_parm (stmt
, inner_rhs
))
1670 /* Match expressions of form &this->field. Those will most likely
1671 combine with something upstream after inlining. */
1672 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1674 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1675 if (TREE_CODE (op
) == PARM_DECL
)
1677 else if (TREE_CODE (op
) == MEM_REF
1678 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1682 /* When parameter is not SSA register because its address is taken
1683 and it is just copied into one, the statement will be completely
1684 free after inlining (we will copy propagate backward). */
1685 if (rhs_free
&& is_gimple_reg (lhs
))
1688 /* Reads of parameters passed by reference
1689 expected to be free (i.e. optimized out after inlining). */
1690 if (TREE_CODE (inner_rhs
) == MEM_REF
1691 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1694 /* Copying parameter passed by reference into gimple register is
1695 probably also going to copy propagate, but we can't be quite
1697 if (rhs_free
&& is_gimple_reg (lhs
))
1700 /* Writes to parameters, parameters passed by value and return value
1701 (either dirrectly or passed via invisible reference) are free.
1703 TODO: We ought to handle testcase like
1704 struct a {int a,b;};
1706 retrurnsturct (void)
1712 This translate into:
1727 For that we either need to copy ipa-split logic detecting writes
1729 if (TREE_CODE (inner_lhs
) == PARM_DECL
1730 || TREE_CODE (inner_lhs
) == RESULT_DECL
1731 || (TREE_CODE (inner_lhs
) == MEM_REF
1732 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1733 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1734 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1735 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1737 0))) == RESULT_DECL
))))
1740 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1742 if (lhs_free
&& rhs_free
)
1752 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1753 predicates to the CFG edges. */
1756 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1757 struct inline_summary
*summary
,
1763 struct agg_position_info aggpos
;
1764 enum tree_code code
, inverted_code
;
1770 last
= last_stmt (bb
);
1771 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1773 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1775 op
= gimple_cond_lhs (last
);
1776 /* TODO: handle conditionals like
1779 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1781 code
= gimple_cond_code (last
);
1782 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1784 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1786 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1787 ? code
: inverted_code
);
1788 /* invert_tree_comparison will return ERROR_MARK on FP
1789 comparsions that are not EQ/NE instead of returning proper
1790 unordered one. Be sure it is not confused with NON_CONSTANT. */
1791 if (this_code
!= ERROR_MARK
)
1793 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1795 gimple_cond_rhs (last
));
1796 e
->aux
= pool_alloc (edge_predicate_pool
);
1797 *(struct predicate
*) e
->aux
= p
;
1802 if (TREE_CODE (op
) != SSA_NAME
)
1805 if (builtin_constant_p (op))
1809 Here we can predicate nonconstant_code. We can't
1810 really handle constant_code since we have no predicate
1811 for this and also the constant code is not known to be
1812 optimized away when inliner doen't see operand is constant.
1813 Other optimizers might think otherwise. */
1814 if (gimple_cond_code (last
) != NE_EXPR
1815 || !integer_zerop (gimple_cond_rhs (last
)))
1817 set_stmt
= SSA_NAME_DEF_STMT (op
);
1818 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1819 || gimple_call_num_args (set_stmt
) != 1)
1821 op2
= gimple_call_arg (set_stmt
, 0);
1822 if (!unmodified_parm_or_parm_agg_item
1823 (info
, set_stmt
, op2
, &index
, &aggpos
))
1825 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1827 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1828 IS_NOT_CONSTANT
, NULL_TREE
);
1829 e
->aux
= pool_alloc (edge_predicate_pool
);
1830 *(struct predicate
*) e
->aux
= p
;
1835 /* If BB ends by a switch we can turn into predicates, attach corresponding
1836 predicates to the CFG edges. */
1839 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1840 struct inline_summary
*summary
,
1846 struct agg_position_info aggpos
;
1852 lastg
= last_stmt (bb
);
1853 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1855 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1856 op
= gimple_switch_index (last
);
1857 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1860 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1862 e
->aux
= pool_alloc (edge_predicate_pool
);
1863 *(struct predicate
*) e
->aux
= false_predicate ();
1865 n
= gimple_switch_num_labels (last
);
1866 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1868 tree cl
= gimple_switch_label (last
, case_idx
);
1872 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1873 min
= CASE_LOW (cl
);
1874 max
= CASE_HIGH (cl
);
1876 /* For default we might want to construct predicate that none
1877 of cases is met, but it is bit hard to do not having negations
1878 of conditionals handy. */
1880 p
= true_predicate ();
1882 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1885 struct predicate p1
, p2
;
1886 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1887 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1888 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1890 *(struct predicate
*) e
->aux
1891 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1896 /* For each BB in NODE attach to its AUX pointer predicate under
1897 which it is executable. */
1900 compute_bb_predicates (struct cgraph_node
*node
,
1901 struct ipa_node_params
*parms_info
,
1902 struct inline_summary
*summary
)
1904 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1908 FOR_EACH_BB_FN (bb
, my_function
)
1910 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1911 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1914 /* Entry block is always executable. */
1915 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1916 = pool_alloc (edge_predicate_pool
);
1917 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1918 = true_predicate ();
1920 /* A simple dataflow propagation of predicates forward in the CFG.
1921 TODO: work in reverse postorder. */
1925 FOR_EACH_BB_FN (bb
, my_function
)
1927 struct predicate p
= false_predicate ();
1930 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1934 struct predicate this_bb_predicate
1935 = *(struct predicate
*) e
->src
->aux
;
1938 = and_predicates (summary
->conds
, &this_bb_predicate
,
1939 (struct predicate
*) e
->aux
);
1940 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1941 if (true_predicate_p (&p
))
1945 if (false_predicate_p (&p
))
1946 gcc_assert (!bb
->aux
);
1952 bb
->aux
= pool_alloc (edge_predicate_pool
);
1953 *((struct predicate
*) bb
->aux
) = p
;
1955 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1957 /* This OR operation is needed to ensure monotonous data flow
1958 in the case we hit the limit on number of clauses and the
1959 and/or operations above give approximate answers. */
1960 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1961 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1964 *((struct predicate
*) bb
->aux
) = p
;
1973 /* We keep info about constantness of SSA names. */
1975 typedef struct predicate predicate_t
;
1976 /* Return predicate specifying when the STMT might have result that is not
1977 a compile time constant. */
1979 static struct predicate
1980 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1981 struct inline_summary
*summary
,
1983 vec
<predicate_t
> nonconstant_names
)
1988 while (UNARY_CLASS_P (expr
))
1989 expr
= TREE_OPERAND (expr
, 0);
1991 parm
= unmodified_parm (NULL
, expr
);
1992 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1993 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1994 if (is_gimple_min_invariant (expr
))
1995 return false_predicate ();
1996 if (TREE_CODE (expr
) == SSA_NAME
)
1997 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1998 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
2000 struct predicate p1
= will_be_nonconstant_expr_predicate
2001 (info
, summary
, TREE_OPERAND (expr
, 0),
2003 struct predicate p2
;
2004 if (true_predicate_p (&p1
))
2006 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2007 TREE_OPERAND (expr
, 1),
2009 return or_predicates (summary
->conds
, &p1
, &p2
);
2011 else if (TREE_CODE (expr
) == COND_EXPR
)
2013 struct predicate p1
= will_be_nonconstant_expr_predicate
2014 (info
, summary
, TREE_OPERAND (expr
, 0),
2016 struct predicate p2
;
2017 if (true_predicate_p (&p1
))
2019 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2020 TREE_OPERAND (expr
, 1),
2022 if (true_predicate_p (&p2
))
2024 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2025 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2026 TREE_OPERAND (expr
, 2),
2028 return or_predicates (summary
->conds
, &p1
, &p2
);
2035 return false_predicate ();
2039 /* Return predicate specifying when the STMT might have result that is not
2040 a compile time constant. */
2042 static struct predicate
2043 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2044 struct inline_summary
*summary
,
2046 vec
<predicate_t
> nonconstant_names
)
2048 struct predicate p
= true_predicate ();
2051 struct predicate op_non_const
;
2054 struct agg_position_info aggpos
;
2056 /* What statments might be optimized away
2057 when their arguments are constant. */
2058 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2059 && gimple_code (stmt
) != GIMPLE_COND
2060 && gimple_code (stmt
) != GIMPLE_SWITCH
2061 && (gimple_code (stmt
) != GIMPLE_CALL
2062 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2065 /* Stores will stay anyway. */
2066 if (gimple_store_p (stmt
))
2069 is_load
= gimple_assign_load_p (stmt
);
2071 /* Loads can be optimized when the value is known. */
2075 gcc_assert (gimple_assign_single_p (stmt
));
2076 op
= gimple_assign_rhs1 (stmt
);
2077 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2084 /* See if we understand all operands before we start
2085 adding conditionals. */
2086 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2088 tree parm
= unmodified_parm (stmt
, use
);
2089 /* For arguments we can build a condition. */
2090 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2092 if (TREE_CODE (use
) != SSA_NAME
)
2094 /* If we know when operand is constant,
2095 we still can say something useful. */
2096 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2103 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2105 op_non_const
= false_predicate ();
2106 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2108 tree parm
= unmodified_parm (stmt
, use
);
2111 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2113 if (index
!= base_index
)
2114 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2119 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2120 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2122 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2123 && gimple_op (stmt
, 0)
2124 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2125 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2127 return op_non_const
;
2130 struct record_modified_bb_info
2136 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2137 set except for info->stmt. */
2140 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2142 struct record_modified_bb_info
*info
=
2143 (struct record_modified_bb_info
*) data
;
2144 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2146 bitmap_set_bit (info
->bb_set
,
2147 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2148 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2149 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2153 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2154 will change since last invocation of STMT.
2156 Value 0 is reserved for compile time invariants.
2157 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2158 ought to be REG_BR_PROB_BASE / estimated_iters. */
2161 param_change_prob (gimple stmt
, int i
)
2163 tree op
= gimple_call_arg (stmt
, i
);
2164 basic_block bb
= gimple_bb (stmt
);
2167 /* Global invariants neve change. */
2168 if (is_gimple_min_invariant (op
))
2170 /* We would have to do non-trivial analysis to really work out what
2171 is the probability of value to change (i.e. when init statement
2172 is in a sibling loop of the call).
2174 We do an conservative estimate: when call is executed N times more often
2175 than the statement defining value, we take the frequency 1/N. */
2176 if (TREE_CODE (op
) == SSA_NAME
)
2181 return REG_BR_PROB_BASE
;
2183 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2184 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2186 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2190 if (init_freq
< bb
->frequency
)
2191 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2193 return REG_BR_PROB_BASE
;
2196 base
= get_base_address (op
);
2201 struct record_modified_bb_info info
;
2204 tree init
= ctor_for_folding (base
);
2206 if (init
!= error_mark_node
)
2209 return REG_BR_PROB_BASE
;
2210 ao_ref_init (&refd
, op
);
2212 info
.bb_set
= BITMAP_ALLOC (NULL
);
2213 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2215 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2217 BITMAP_FREE (info
.bb_set
);
2218 return REG_BR_PROB_BASE
;
2221 /* Assume that every memory is initialized at entry.
2222 TODO: Can we easilly determine if value is always defined
2223 and thus we may skip entry block? */
2224 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2225 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2229 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2230 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2232 BITMAP_FREE (info
.bb_set
);
2233 if (max
< bb
->frequency
)
2234 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2236 return REG_BR_PROB_BASE
;
2238 return REG_BR_PROB_BASE
;
2241 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2242 sub-graph and if the predicate the condition depends on is known. If so,
2243 return true and store the pointer the predicate in *P. */
2246 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2247 inline_summary
*summary
, basic_block bb
,
2248 struct predicate
*p
,
2249 vec
<predicate_t
> nonconstant_names
)
2253 basic_block first_bb
= NULL
;
2256 if (single_pred_p (bb
))
2258 *p
= false_predicate ();
2262 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2264 if (single_succ_p (e
->src
))
2266 if (!single_pred_p (e
->src
))
2269 first_bb
= single_pred (e
->src
);
2270 else if (single_pred (e
->src
) != first_bb
)
2277 else if (e
->src
!= first_bb
)
2285 stmt
= last_stmt (first_bb
);
2287 || gimple_code (stmt
) != GIMPLE_COND
2288 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2291 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2292 gimple_cond_lhs (stmt
),
2294 if (true_predicate_p (p
))
2300 /* Given a PHI statement in a function described by inline properties SUMMARY
2301 and *P being the predicate describing whether the selected PHI argument is
2302 known, store a predicate for the result of the PHI statement into
2303 NONCONSTANT_NAMES, if possible. */
2306 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2307 struct predicate
*p
,
2308 vec
<predicate_t
> nonconstant_names
)
2312 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2314 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2315 if (!is_gimple_min_invariant (arg
))
2317 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2318 *p
= or_predicates (summary
->conds
, p
,
2319 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2320 if (true_predicate_p (p
))
2325 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2327 fprintf (dump_file
, "\t\tphi predicate: ");
2328 dump_predicate (dump_file
, summary
->conds
, p
);
2330 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2333 /* Return predicate specifying when array index in access OP becomes non-constant. */
2335 static struct predicate
2336 array_index_predicate (inline_summary
*info
,
2337 vec
< predicate_t
> nonconstant_names
, tree op
)
2339 struct predicate p
= false_predicate ();
2340 while (handled_component_p (op
))
2342 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2344 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2345 p
= or_predicates (info
->conds
, &p
,
2346 &nonconstant_names
[SSA_NAME_VERSION
2347 (TREE_OPERAND (op
, 1))]);
2349 op
= TREE_OPERAND (op
, 0);
2354 /* For a typical usage of __builtin_expect (a<b, 1), we
2355 may introduce an extra relation stmt:
2356 With the builtin, we have
2359 t3 = __builtin_expect (t2, 1);
2362 Without the builtin, we have
2365 This affects the size/time estimation and may have
2366 an impact on the earlier inlining.
2367 Here find this pattern and fix it up later. */
2370 find_foldable_builtin_expect (basic_block bb
)
2372 gimple_stmt_iterator bsi
;
2374 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2376 gimple stmt
= gsi_stmt (bsi
);
2377 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2378 || (is_gimple_call (stmt
)
2379 && gimple_call_internal_p (stmt
)
2380 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2382 tree var
= gimple_call_lhs (stmt
);
2383 tree arg
= gimple_call_arg (stmt
, 0);
2384 use_operand_p use_p
;
2391 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2393 while (TREE_CODE (arg
) == SSA_NAME
)
2395 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2396 if (!is_gimple_assign (stmt_tmp
))
2398 switch (gimple_assign_rhs_code (stmt_tmp
))
2417 arg
= gimple_assign_rhs1 (stmt_tmp
);
2420 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2421 && gimple_code (use_stmt
) == GIMPLE_COND
)
2428 /* Return true when the basic blocks contains only clobbers followed by RESX.
2429 Such BBs are kept around to make removal of dead stores possible with
2430 presence of EH and will be optimized out by optimize_clobbers later in the
2433 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2434 that can be clobber only, too.. When it is false, the RESX is not necessary
2435 on the end of basic block. */
2438 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2440 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2446 if (gsi_end_p (gsi
))
2448 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2452 else if (!single_succ_p (bb
))
2455 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2457 gimple stmt
= gsi_stmt (gsi
);
2458 if (is_gimple_debug (stmt
))
2460 if (gimple_clobber_p (stmt
))
2462 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2467 /* See if all predecestors are either throws or clobber only BBs. */
2468 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2469 if (!(e
->flags
& EDGE_EH
)
2470 && !clobber_only_eh_bb_p (e
->src
, false))
2476 /* Compute function body size parameters for NODE.
2477 When EARLY is true, we compute only simple summaries without
2478 non-trivial predicates to drive the early inliner. */
2481 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2484 /* Estimate static overhead for function prologue/epilogue and alignment. */
2486 /* Benefits are scaled by probability of elimination that is in range
2489 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2491 struct inline_summary
*info
= inline_summaries
->get (node
);
2492 struct predicate bb_predicate
;
2493 struct ipa_node_params
*parms_info
= NULL
;
2494 vec
<predicate_t
> nonconstant_names
= vNULL
;
2497 predicate array_index
= true_predicate ();
2498 gimple fix_builtin_expect_stmt
;
2503 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2504 so we can produce proper inline hints.
2506 When optimizing and analyzing for early inliner, initialize node params
2507 so we can produce correct BB predicates. */
2509 if (opt_for_fn (node
->decl
, optimize
))
2511 calculate_dominance_info (CDI_DOMINATORS
);
2513 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2516 ipa_check_create_node_params ();
2517 ipa_initialize_node_params (node
);
2520 if (ipa_node_params_sum
)
2522 parms_info
= IPA_NODE_REF (node
);
2523 nonconstant_names
.safe_grow_cleared
2524 (SSANAMES (my_function
)->length ());
2529 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2532 /* When we run into maximal number of entries, we assign everything to the
2533 constant truth case. Be sure to have it in list. */
2534 bb_predicate
= true_predicate ();
2535 account_size_time (info
, 0, 0, &bb_predicate
);
2537 bb_predicate
= not_inlined_predicate ();
2538 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2540 gcc_assert (my_function
&& my_function
->cfg
);
2542 compute_bb_predicates (node
, parms_info
, info
);
2543 gcc_assert (cfun
== my_function
);
2544 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2545 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2546 for (n
= 0; n
< nblocks
; n
++)
2548 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2549 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2550 if (clobber_only_eh_bb_p (bb
))
2552 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2553 fprintf (dump_file
, "\n Ignoring BB %i;"
2554 " it will be optimized away by cleanup_clobbers\n",
2559 /* TODO: Obviously predicates can be propagated down across CFG. */
2563 bb_predicate
= *(struct predicate
*) bb
->aux
;
2565 bb_predicate
= false_predicate ();
2568 bb_predicate
= true_predicate ();
2570 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2572 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2573 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2576 if (parms_info
&& nonconstant_names
.exists ())
2578 struct predicate phi_predicate
;
2579 bool first_phi
= true;
2581 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2585 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2590 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2592 fprintf (dump_file
, " ");
2593 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2595 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2600 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2602 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2605 gimple stmt
= gsi_stmt (bsi
);
2606 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2607 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2609 struct predicate will_be_nonconstant
;
2611 /* This relation stmt should be folded after we remove
2612 buildin_expect call. Adjust the cost here. */
2613 if (stmt
== fix_builtin_expect_stmt
)
2619 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2621 fprintf (dump_file
, " ");
2622 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2623 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2624 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2628 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2630 struct predicate this_array_index
;
2632 array_index_predicate (info
, nonconstant_names
,
2633 gimple_assign_rhs1 (stmt
));
2634 if (!false_predicate_p (&this_array_index
))
2636 and_predicates (info
->conds
, &array_index
,
2639 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2641 struct predicate this_array_index
;
2643 array_index_predicate (info
, nonconstant_names
,
2644 gimple_get_lhs (stmt
));
2645 if (!false_predicate_p (&this_array_index
))
2647 and_predicates (info
->conds
, &array_index
,
2652 if (is_gimple_call (stmt
)
2653 && !gimple_call_internal_p (stmt
))
2655 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2656 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2658 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2659 resolved as constant. We however don't want to optimize
2660 out the cgraph edges. */
2661 if (nonconstant_names
.exists ()
2662 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2663 && gimple_call_lhs (stmt
)
2664 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2666 struct predicate false_p
= false_predicate ();
2667 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2670 if (ipa_node_params_sum
)
2672 int count
= gimple_call_num_args (stmt
);
2676 es
->param
.safe_grow_cleared (count
);
2677 for (i
= 0; i
< count
; i
++)
2679 int prob
= param_change_prob (stmt
, i
);
2680 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2681 es
->param
[i
].change_prob
= prob
;
2685 es
->call_stmt_size
= this_size
;
2686 es
->call_stmt_time
= this_time
;
2687 es
->loop_depth
= bb_loop_depth (bb
);
2688 edge_set_predicate (edge
, &bb_predicate
);
2691 /* TODO: When conditional jump or swithc is known to be constant, but
2692 we did not translate it into the predicates, we really can account
2693 just maximum of the possible paths. */
2696 = will_be_nonconstant_predicate (parms_info
, info
,
2697 stmt
, nonconstant_names
);
2698 if (this_time
|| this_size
)
2704 prob
= eliminated_by_inlining_prob (stmt
);
2705 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2707 "\t\t50%% will be eliminated by inlining\n");
2708 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2709 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2712 p
= and_predicates (info
->conds
, &bb_predicate
,
2713 &will_be_nonconstant
);
2715 p
= true_predicate ();
2717 if (!false_predicate_p (&p
)
2718 || (is_gimple_call (stmt
)
2719 && !false_predicate_p (&bb_predicate
)))
2723 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2724 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2727 /* We account everything but the calls. Calls have their own
2728 size/time info attached to cgraph edges. This is necessary
2729 in order to make the cost disappear after inlining. */
2730 if (!is_gimple_call (stmt
))
2734 struct predicate ip
= not_inlined_predicate ();
2735 ip
= and_predicates (info
->conds
, &ip
, &p
);
2736 account_size_time (info
, this_size
* prob
,
2737 this_time
* prob
, &ip
);
2740 account_size_time (info
, this_size
* (2 - prob
),
2741 this_time
* (2 - prob
), &p
);
2744 gcc_assert (time
>= 0);
2745 gcc_assert (size
>= 0);
2749 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2750 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2751 if (time
> MAX_TIME
)
2755 if (nonconstant_names
.exists () && !early
)
2758 predicate loop_iterations
= true_predicate ();
2759 predicate loop_stride
= true_predicate ();
2761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2762 flow_loops_dump (dump_file
, NULL
, 0);
2764 FOR_EACH_LOOP (loop
, 0)
2769 struct tree_niter_desc niter_desc
;
2770 basic_block
*body
= get_loop_body (loop
);
2771 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2773 exits
= get_loop_exit_edges (loop
);
2774 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2775 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2776 && !is_gimple_min_invariant (niter_desc
.niter
))
2778 predicate will_be_nonconstant
2779 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2782 if (!true_predicate_p (&will_be_nonconstant
))
2783 will_be_nonconstant
= and_predicates (info
->conds
,
2785 &will_be_nonconstant
);
2786 if (!true_predicate_p (&will_be_nonconstant
)
2787 && !false_predicate_p (&will_be_nonconstant
))
2788 /* This is slightly inprecise. We may want to represent each
2789 loop with independent predicate. */
2791 and_predicates (info
->conds
, &loop_iterations
,
2792 &will_be_nonconstant
);
2796 for (i
= 0; i
< loop
->num_nodes
; i
++)
2798 gimple_stmt_iterator gsi
;
2799 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2800 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2803 gimple stmt
= gsi_stmt (gsi
);
2808 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2810 predicate will_be_nonconstant
;
2813 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2814 || is_gimple_min_invariant (iv
.step
))
2817 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2820 if (!true_predicate_p (&will_be_nonconstant
))
2822 = and_predicates (info
->conds
,
2824 &will_be_nonconstant
);
2825 if (!true_predicate_p (&will_be_nonconstant
)
2826 && !false_predicate_p (&will_be_nonconstant
))
2827 /* This is slightly inprecise. We may want to represent
2828 each loop with independent predicate. */
2830 and_predicates (info
->conds
, &loop_stride
,
2831 &will_be_nonconstant
);
2837 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2839 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
, loop_stride
);
2842 FOR_ALL_BB_FN (bb
, my_function
)
2848 pool_free (edge_predicate_pool
, bb
->aux
);
2850 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2853 pool_free (edge_predicate_pool
, e
->aux
);
2857 inline_summaries
->get (node
)->self_time
= time
;
2858 inline_summaries
->get (node
)->self_size
= size
;
2859 nonconstant_names
.release ();
2860 if (opt_for_fn (node
->decl
, optimize
))
2863 loop_optimizer_finalize ();
2864 else if (!ipa_edge_args_vector
)
2865 ipa_free_all_node_params ();
2866 free_dominance_info (CDI_DOMINATORS
);
2870 fprintf (dump_file
, "\n");
2871 dump_inline_summary (dump_file
, node
);
2876 /* Compute parameters of functions used by inliner.
2877 EARLY is true when we compute parameters for the early inliner */
2880 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2882 HOST_WIDE_INT self_stack_size
;
2883 struct cgraph_edge
*e
;
2884 struct inline_summary
*info
;
2886 gcc_assert (!node
->global
.inlined_to
);
2888 inline_summary_alloc ();
2890 info
= inline_summaries
->get (node
);
2891 reset_inline_summary (node
, info
);
2893 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2894 Once this happen, we will need to more curefully predict call
2896 if (node
->thunk
.thunk_p
)
2898 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2899 struct predicate t
= true_predicate ();
2901 info
->inlinable
= 0;
2902 node
->callees
->call_stmt_cannot_inline_p
= true;
2903 node
->local
.can_change_signature
= false;
2904 es
->call_stmt_time
= 1;
2905 es
->call_stmt_size
= 1;
2906 account_size_time (info
, 0, 0, &t
);
2910 /* Even is_gimple_min_invariant rely on current_function_decl. */
2911 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2913 /* Estimate the stack size for the function if we're optimizing. */
2914 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2915 info
->estimated_self_stack_size
= self_stack_size
;
2916 info
->estimated_stack_size
= self_stack_size
;
2917 info
->stack_frame_offset
= 0;
2919 /* Can this function be inlined at all? */
2920 if (!opt_for_fn (node
->decl
, optimize
)
2921 && !lookup_attribute ("always_inline",
2922 DECL_ATTRIBUTES (node
->decl
)))
2923 info
->inlinable
= false;
2925 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2927 /* Type attributes can use parameter indices to describe them. */
2928 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2929 node
->local
.can_change_signature
= false;
2932 /* Otherwise, inlinable functions always can change signature. */
2933 if (info
->inlinable
)
2934 node
->local
.can_change_signature
= true;
2937 /* Functions calling builtin_apply can not change signature. */
2938 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2940 tree
cdecl = e
->callee
->decl
;
2941 if (DECL_BUILT_IN (cdecl)
2942 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2943 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2944 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2947 node
->local
.can_change_signature
= !e
;
2950 estimate_function_body_sizes (node
, early
);
2952 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2953 if (e
->callee
->comdat_local_p ())
2955 node
->calls_comdat_local
= (e
!= NULL
);
2957 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2958 info
->time
= info
->self_time
;
2959 info
->size
= info
->self_size
;
2960 info
->stack_frame_offset
= 0;
2961 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2962 #ifdef ENABLE_CHECKING
2963 inline_update_overall_summary (node
);
2964 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2971 /* Compute parameters of functions used by inliner using
2972 current_function_decl. */
2975 compute_inline_parameters_for_current (void)
2977 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2983 const pass_data pass_data_inline_parameters
=
2985 GIMPLE_PASS
, /* type */
2986 "inline_param", /* name */
2987 OPTGROUP_INLINE
, /* optinfo_flags */
2988 TV_INLINE_PARAMETERS
, /* tv_id */
2989 0, /* properties_required */
2990 0, /* properties_provided */
2991 0, /* properties_destroyed */
2992 0, /* todo_flags_start */
2993 0, /* todo_flags_finish */
2996 class pass_inline_parameters
: public gimple_opt_pass
2999 pass_inline_parameters (gcc::context
*ctxt
)
3000 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
3003 /* opt_pass methods: */
3004 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
3005 virtual unsigned int execute (function
*)
3007 return compute_inline_parameters_for_current ();
3010 }; // class pass_inline_parameters
3015 make_pass_inline_parameters (gcc::context
*ctxt
)
3017 return new pass_inline_parameters (ctxt
);
3021 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3022 KNOWN_CONTEXTS and KNOWN_AGGS. */
3025 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3026 int *size
, int *time
,
3027 vec
<tree
> known_vals
,
3028 vec
<ipa_polymorphic_call_context
> known_contexts
,
3029 vec
<ipa_agg_jump_function_p
> known_aggs
)
3032 struct cgraph_node
*callee
;
3033 struct inline_summary
*isummary
;
3034 enum availability avail
;
3037 if (!known_vals
.exists () && !known_contexts
.exists ())
3039 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3042 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3043 known_aggs
, &speculative
);
3044 if (!target
|| speculative
)
3047 /* Account for difference in cost between indirect and direct calls. */
3048 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3049 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3050 gcc_checking_assert (*time
>= 0);
3051 gcc_checking_assert (*size
>= 0);
3053 callee
= cgraph_node::get (target
);
3054 if (!callee
|| !callee
->definition
)
3056 callee
= callee
->function_symbol (&avail
);
3057 if (avail
< AVAIL_AVAILABLE
)
3059 isummary
= inline_summaries
->get (callee
);
3060 return isummary
->inlinable
;
3063 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3064 handle edge E with probability PROB.
3065 Set HINTS if edge may be devirtualized.
3066 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3070 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3073 vec
<tree
> known_vals
,
3074 vec
<ipa_polymorphic_call_context
> known_contexts
,
3075 vec
<ipa_agg_jump_function_p
> known_aggs
,
3076 inline_hints
*hints
)
3078 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3079 int call_size
= es
->call_stmt_size
;
3080 int call_time
= es
->call_stmt_time
;
3083 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3084 known_vals
, known_contexts
, known_aggs
)
3085 && hints
&& e
->maybe_hot_p ())
3086 *hints
|= INLINE_HINT_indirect_call
;
3087 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3090 *min_size
+= cur_size
;
3091 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3092 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3093 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3094 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3099 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3100 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3101 describe context of the call site. */
3104 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3105 int *min_size
, int *time
,
3106 inline_hints
*hints
,
3107 clause_t possible_truths
,
3108 vec
<tree
> known_vals
,
3109 vec
<ipa_polymorphic_call_context
> known_contexts
,
3110 vec
<ipa_agg_jump_function_p
> known_aggs
)
3112 struct cgraph_edge
*e
;
3113 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3115 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3117 /* Do not care about zero sized builtins. */
3118 if (e
->inline_failed
&& !es
->call_stmt_size
)
3120 gcc_checking_assert (!es
->call_stmt_time
);
3124 || evaluate_predicate (es
->predicate
, possible_truths
))
3126 if (e
->inline_failed
)
3128 /* Predicates of calls shall not use NOT_CHANGED codes,
3129 sowe do not need to compute probabilities. */
3130 estimate_edge_size_and_time (e
, size
,
3131 es
->predicate
? NULL
: min_size
,
3132 time
, REG_BR_PROB_BASE
,
3133 known_vals
, known_contexts
,
3137 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3140 known_vals
, known_contexts
,
3144 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3146 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3148 || evaluate_predicate (es
->predicate
, possible_truths
))
3149 estimate_edge_size_and_time (e
, size
,
3150 es
->predicate
? NULL
: min_size
,
3151 time
, REG_BR_PROB_BASE
,
3152 known_vals
, known_contexts
, known_aggs
,
3158 /* Estimate size and time needed to execute NODE assuming
3159 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3160 information about NODE's arguments. If non-NULL use also probability
3161 information present in INLINE_PARAM_SUMMARY vector.
3162 Additionally detemine hints determined by the context. Finally compute
3163 minimal size needed for the call that is independent on the call context and
3164 can be used for fast estimates. Return the values in RET_SIZE,
3165 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3168 estimate_node_size_and_time (struct cgraph_node
*node
,
3169 clause_t possible_truths
,
3170 vec
<tree
> known_vals
,
3171 vec
<ipa_polymorphic_call_context
> known_contexts
,
3172 vec
<ipa_agg_jump_function_p
> known_aggs
,
3173 int *ret_size
, int *ret_min_size
, int *ret_time
,
3174 inline_hints
*ret_hints
,
3175 vec
<inline_param_summary
>
3176 inline_param_summary
)
3178 struct inline_summary
*info
= inline_summaries
->get (node
);
3183 inline_hints hints
= 0;
3186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3189 fprintf (dump_file
, " Estimating body: %s/%i\n"
3190 " Known to be false: ", node
->name (),
3193 for (i
= predicate_not_inlined_condition
;
3194 i
< (predicate_first_dynamic_condition
3195 + (int) vec_safe_length (info
->conds
)); i
++)
3196 if (!(possible_truths
& (1 << i
)))
3199 fprintf (dump_file
, ", ");
3201 dump_condition (dump_file
, info
->conds
, i
);
3205 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3206 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3209 gcc_checking_assert (e
->time
>= 0);
3210 gcc_checking_assert (time
>= 0);
3211 if (!inline_param_summary
.exists ())
3215 int prob
= predicate_probability (info
->conds
,
3218 inline_param_summary
);
3219 gcc_checking_assert (prob
>= 0);
3220 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3221 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3223 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3224 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3225 gcc_checking_assert (time
>= 0);
3228 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3229 min_size
= (*info
->entry
)[0].size
;
3230 gcc_checking_assert (size
>= 0);
3231 gcc_checking_assert (time
>= 0);
3233 if (info
->loop_iterations
3234 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3235 hints
|= INLINE_HINT_loop_iterations
;
3236 if (info
->loop_stride
3237 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3238 hints
|= INLINE_HINT_loop_stride
;
3239 if (info
->array_index
3240 && !evaluate_predicate (info
->array_index
, possible_truths
))
3241 hints
|= INLINE_HINT_array_index
;
3243 hints
|= INLINE_HINT_in_scc
;
3244 if (DECL_DECLARED_INLINE_P (node
->decl
))
3245 hints
|= INLINE_HINT_declared_inline
;
3247 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3248 known_vals
, known_contexts
, known_aggs
);
3249 gcc_checking_assert (size
>= 0);
3250 gcc_checking_assert (time
>= 0);
3251 time
= RDIV (time
, INLINE_TIME_SCALE
);
3252 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3253 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3255 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3256 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3262 *ret_min_size
= min_size
;
3269 /* Estimate size and time needed to execute callee of EDGE assuming that
3270 parameters known to be constant at caller of EDGE are propagated.
3271 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3272 and types for parameters. */
3275 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3276 vec
<tree
> known_vals
,
3277 vec
<ipa_polymorphic_call_context
>
3279 vec
<ipa_agg_jump_function_p
> known_aggs
,
3280 int *ret_size
, int *ret_time
,
3281 inline_hints
*hints
)
3285 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3287 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3288 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3291 /* Translate all conditions from callee representation into caller
3292 representation and symbolically evaluate predicate P into new predicate.
3294 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3295 is summary of function predicate P is from. OPERAND_MAP is array giving
3296 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3297 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3298 predicate under which callee is executed. OFFSET_MAP is an array of of
3299 offsets that need to be added to conditions, negative offset means that
3300 conditions relying on values passed by reference have to be discarded
3301 because they might not be preserved (and should be considered offset zero
3302 for other purposes). */
3304 static struct predicate
3305 remap_predicate (struct inline_summary
*info
,
3306 struct inline_summary
*callee_info
,
3307 struct predicate
*p
,
3308 vec
<int> operand_map
,
3309 vec
<int> offset_map
,
3310 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3313 struct predicate out
= true_predicate ();
3315 /* True predicate is easy. */
3316 if (true_predicate_p (p
))
3317 return *toplev_predicate
;
3318 for (i
= 0; p
->clause
[i
]; i
++)
3320 clause_t clause
= p
->clause
[i
];
3322 struct predicate clause_predicate
= false_predicate ();
3324 gcc_assert (i
< MAX_CLAUSES
);
3326 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3327 /* Do we have condition we can't disprove? */
3328 if (clause
& possible_truths
& (1 << cond
))
3330 struct predicate cond_predicate
;
3331 /* Work out if the condition can translate to predicate in the
3332 inlined function. */
3333 if (cond
>= predicate_first_dynamic_condition
)
3335 struct condition
*c
;
3337 c
= &(*callee_info
->conds
)[cond
3339 predicate_first_dynamic_condition
];
3340 /* See if we can remap condition operand to caller's operand.
3341 Otherwise give up. */
3342 if (!operand_map
.exists ()
3343 || (int) operand_map
.length () <= c
->operand_num
3344 || operand_map
[c
->operand_num
] == -1
3345 /* TODO: For non-aggregate conditions, adding an offset is
3346 basically an arithmetic jump function processing which
3347 we should support in future. */
3348 || ((!c
->agg_contents
|| !c
->by_ref
)
3349 && offset_map
[c
->operand_num
] > 0)
3350 || (c
->agg_contents
&& c
->by_ref
3351 && offset_map
[c
->operand_num
] < 0))
3352 cond_predicate
= true_predicate ();
3355 struct agg_position_info ap
;
3356 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3357 if (offset_delta
< 0)
3359 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3362 gcc_assert (!c
->agg_contents
3363 || c
->by_ref
|| offset_delta
== 0);
3364 ap
.offset
= c
->offset
+ offset_delta
;
3365 ap
.agg_contents
= c
->agg_contents
;
3366 ap
.by_ref
= c
->by_ref
;
3367 cond_predicate
= add_condition (info
,
3368 operand_map
[c
->operand_num
],
3369 &ap
, c
->code
, c
->val
);
3372 /* Fixed conditions remains same, construct single
3373 condition predicate. */
3376 cond_predicate
.clause
[0] = 1 << cond
;
3377 cond_predicate
.clause
[1] = 0;
3379 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3382 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3384 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3388 /* Update summary information of inline clones after inlining.
3389 Compute peak stack usage. */
3392 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3394 struct cgraph_edge
*e
;
3395 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3396 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3399 callee_info
->stack_frame_offset
3400 = caller_info
->stack_frame_offset
3401 + caller_info
->estimated_self_stack_size
;
3402 peak
= callee_info
->stack_frame_offset
3403 + callee_info
->estimated_self_stack_size
;
3404 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3405 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3406 ipa_propagate_frequency (node
);
3407 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3409 if (!e
->inline_failed
)
3410 inline_update_callee_summaries (e
->callee
, depth
);
3411 inline_edge_summary (e
)->loop_depth
+= depth
;
3413 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3414 inline_edge_summary (e
)->loop_depth
+= depth
;
3417 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3418 When functoin A is inlined in B and A calls C with parameter that
3419 changes with probability PROB1 and C is known to be passthroug
3420 of argument if B that change with probability PROB2, the probability
3421 of change is now PROB1*PROB2. */
3424 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3425 struct cgraph_edge
*edge
)
3427 if (ipa_node_params_sum
)
3430 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3431 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3432 struct inline_edge_summary
*inlined_es
3433 = inline_edge_summary (inlined_edge
);
3435 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3437 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3438 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3439 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3440 < (int) inlined_es
->param
.length ()))
3442 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3443 int prob1
= es
->param
[i
].change_prob
;
3444 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3445 int prob
= combine_probabilities (prob1
, prob2
);
3447 if (prob1
&& prob2
&& !prob
)
3450 es
->param
[i
].change_prob
= prob
;
3456 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3458 Remap predicates of callees of NODE. Rest of arguments match
3461 Also update change probabilities. */
3464 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3465 struct cgraph_node
*node
,
3466 struct inline_summary
*info
,
3467 struct inline_summary
*callee_info
,
3468 vec
<int> operand_map
,
3469 vec
<int> offset_map
,
3470 clause_t possible_truths
,
3471 struct predicate
*toplev_predicate
)
3473 struct cgraph_edge
*e
;
3474 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3476 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3479 if (e
->inline_failed
)
3481 remap_edge_change_prob (inlined_edge
, e
);
3485 p
= remap_predicate (info
, callee_info
,
3486 es
->predicate
, operand_map
, offset_map
,
3487 possible_truths
, toplev_predicate
);
3488 edge_set_predicate (e
, &p
);
3489 /* TODO: We should remove the edge for code that will be
3490 optimized out, but we need to keep verifiers and tree-inline
3491 happy. Make it cold for now. */
3492 if (false_predicate_p (&p
))
3499 edge_set_predicate (e
, toplev_predicate
);
3502 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3503 operand_map
, offset_map
, possible_truths
,
3506 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3508 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3511 remap_edge_change_prob (inlined_edge
, e
);
3514 p
= remap_predicate (info
, callee_info
,
3515 es
->predicate
, operand_map
, offset_map
,
3516 possible_truths
, toplev_predicate
);
3517 edge_set_predicate (e
, &p
);
3518 /* TODO: We should remove the edge for code that will be optimized
3519 out, but we need to keep verifiers and tree-inline happy.
3520 Make it cold for now. */
3521 if (false_predicate_p (&p
))
3528 edge_set_predicate (e
, toplev_predicate
);
3532 /* Same as remap_predicate, but set result into hint *HINT. */
3535 remap_hint_predicate (struct inline_summary
*info
,
3536 struct inline_summary
*callee_info
,
3537 struct predicate
**hint
,
3538 vec
<int> operand_map
,
3539 vec
<int> offset_map
,
3540 clause_t possible_truths
,
3541 struct predicate
*toplev_predicate
)
3547 p
= remap_predicate (info
, callee_info
,
3549 operand_map
, offset_map
,
3550 possible_truths
, toplev_predicate
);
3551 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3554 set_hint_predicate (hint
, p
);
3556 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3560 /* We inlined EDGE. Update summary of the function we inlined into. */
3563 inline_merge_summary (struct cgraph_edge
*edge
)
3565 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3566 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3567 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3568 struct inline_summary
*info
= inline_summaries
->get (to
);
3569 clause_t clause
= 0; /* not_inline is known to be false. */
3571 vec
<int> operand_map
= vNULL
;
3572 vec
<int> offset_map
= vNULL
;
3574 struct predicate toplev_predicate
;
3575 struct predicate true_p
= true_predicate ();
3576 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3579 toplev_predicate
= *es
->predicate
;
3581 toplev_predicate
= true_predicate ();
3583 if (callee_info
->conds
)
3584 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3585 if (ipa_node_params_sum
&& callee_info
->conds
)
3587 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3588 int count
= ipa_get_cs_argument_count (args
);
3593 operand_map
.safe_grow_cleared (count
);
3594 offset_map
.safe_grow_cleared (count
);
3596 for (i
= 0; i
< count
; i
++)
3598 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3601 /* TODO: handle non-NOPs when merging. */
3602 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3604 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3605 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3606 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3609 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3611 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3612 if (offset
>= 0 && offset
< INT_MAX
)
3614 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3615 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3617 offset_map
[i
] = offset
;
3620 operand_map
[i
] = map
;
3621 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3624 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3626 struct predicate p
= remap_predicate (info
, callee_info
,
3627 &e
->predicate
, operand_map
,
3630 if (!false_predicate_p (&p
))
3632 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3633 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3634 int prob
= predicate_probability (callee_info
->conds
,
3637 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3638 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3639 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3640 if (prob
!= REG_BR_PROB_BASE
3641 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3643 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3644 (double) prob
/ REG_BR_PROB_BASE
);
3646 account_size_time (info
, e
->size
, add_time
, &p
);
3649 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3650 offset_map
, clause
, &toplev_predicate
);
3651 remap_hint_predicate (info
, callee_info
,
3652 &callee_info
->loop_iterations
,
3653 operand_map
, offset_map
, clause
, &toplev_predicate
);
3654 remap_hint_predicate (info
, callee_info
,
3655 &callee_info
->loop_stride
,
3656 operand_map
, offset_map
, clause
, &toplev_predicate
);
3657 remap_hint_predicate (info
, callee_info
,
3658 &callee_info
->array_index
,
3659 operand_map
, offset_map
, clause
, &toplev_predicate
);
3661 inline_update_callee_summaries (edge
->callee
,
3662 inline_edge_summary (edge
)->loop_depth
);
3664 /* We do not maintain predicates of inlined edges, free it. */
3665 edge_set_predicate (edge
, &true_p
);
3666 /* Similarly remove param summaries. */
3667 es
->param
.release ();
3668 operand_map
.release ();
3669 offset_map
.release ();
3672 /* For performance reasons inline_merge_summary is not updating overall size
3673 and time. Recompute it. */
3676 inline_update_overall_summary (struct cgraph_node
*node
)
3678 struct inline_summary
*info
= inline_summaries
->get (node
);
3684 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3686 info
->size
+= e
->size
, info
->time
+= e
->time
;
3687 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3688 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3690 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3692 ~(clause_t
) (1 << predicate_false_condition
),
3693 vNULL
, vNULL
, vNULL
);
3694 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3695 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3698 /* Return hints derrived from EDGE. */
3700 simple_edge_hints (struct cgraph_edge
*edge
)
3703 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3704 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3705 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
3706 if (inline_summaries
->get (to
)->scc_no
3707 && inline_summaries
->get (to
)->scc_no
3708 == inline_summaries
->get (callee
)->scc_no
3709 && !edge
->recursive_p ())
3710 hints
|= INLINE_HINT_same_scc
;
3712 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
3713 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
3715 hints
|= INLINE_HINT_cross_module
;
3720 /* Estimate the time cost for the caller when inlining EDGE.
3721 Only to be called via estimate_edge_time, that handles the
3724 When caching, also update the cache entry. Compute both time and
3725 size, since we always need both metrics eventually. */
3728 do_estimate_edge_time (struct cgraph_edge
*edge
)
3733 struct cgraph_node
*callee
;
3735 vec
<tree
> known_vals
;
3736 vec
<ipa_polymorphic_call_context
> known_contexts
;
3737 vec
<ipa_agg_jump_function_p
> known_aggs
;
3738 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3741 callee
= edge
->callee
->ultimate_alias_target ();
3743 gcc_checking_assert (edge
->inline_failed
);
3744 evaluate_properties_for_edge (edge
, true,
3745 &clause
, &known_vals
, &known_contexts
,
3747 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3748 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3750 /* When we have profile feedback, we can quite safely identify hot
3751 edges and for those we disable size limits. Don't do that when
3752 probability that caller will call the callee is low however, since it
3753 may hurt optimization of the caller's hot path. */
3754 if (edge
->count
&& edge
->maybe_hot_p ()
3756 > (edge
->caller
->global
.inlined_to
3757 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3758 hints
|= INLINE_HINT_known_hot
;
3760 known_vals
.release ();
3761 known_contexts
.release ();
3762 known_aggs
.release ();
3763 gcc_checking_assert (size
>= 0);
3764 gcc_checking_assert (time
>= 0);
3766 /* When caching, update the cache entry. */
3767 if (edge_growth_cache
.exists ())
3769 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3770 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3771 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3772 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3774 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3775 hints
|= simple_edge_hints (edge
);
3776 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3782 /* Return estimated callee growth after inlining EDGE.
3783 Only to be called via estimate_edge_size. */
3786 do_estimate_edge_size (struct cgraph_edge
*edge
)
3789 struct cgraph_node
*callee
;
3791 vec
<tree
> known_vals
;
3792 vec
<ipa_polymorphic_call_context
> known_contexts
;
3793 vec
<ipa_agg_jump_function_p
> known_aggs
;
3795 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3797 if (edge_growth_cache
.exists ())
3799 do_estimate_edge_time (edge
);
3800 size
= edge_growth_cache
[edge
->uid
].size
;
3801 gcc_checking_assert (size
);
3802 return size
- (size
> 0);
3805 callee
= edge
->callee
->ultimate_alias_target ();
3807 /* Early inliner runs without caching, go ahead and do the dirty work. */
3808 gcc_checking_assert (edge
->inline_failed
);
3809 evaluate_properties_for_edge (edge
, true,
3810 &clause
, &known_vals
, &known_contexts
,
3812 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3813 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3814 known_vals
.release ();
3815 known_contexts
.release ();
3816 known_aggs
.release ();
3821 /* Estimate the growth of the caller when inlining EDGE.
3822 Only to be called via estimate_edge_size. */
3825 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3828 struct cgraph_node
*callee
;
3830 vec
<tree
> known_vals
;
3831 vec
<ipa_polymorphic_call_context
> known_contexts
;
3832 vec
<ipa_agg_jump_function_p
> known_aggs
;
3834 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3836 if (edge_growth_cache
.exists ())
3838 do_estimate_edge_time (edge
);
3839 hints
= edge_growth_cache
[edge
->uid
].hints
;
3840 gcc_checking_assert (hints
);
3844 callee
= edge
->callee
->ultimate_alias_target ();
3846 /* Early inliner runs without caching, go ahead and do the dirty work. */
3847 gcc_checking_assert (edge
->inline_failed
);
3848 evaluate_properties_for_edge (edge
, true,
3849 &clause
, &known_vals
, &known_contexts
,
3851 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3852 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3853 known_vals
.release ();
3854 known_contexts
.release ();
3855 known_aggs
.release ();
3856 hints
|= simple_edge_hints (edge
);
3861 /* Estimate self time of the function NODE after inlining EDGE. */
3864 estimate_time_after_inlining (struct cgraph_node
*node
,
3865 struct cgraph_edge
*edge
)
3867 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3868 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3871 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3874 if (time
> MAX_TIME
)
3878 return inline_summaries
->get (node
)->time
;
3882 /* Estimate the size of NODE after inlining EDGE which should be an
3883 edge to either NODE or a call inlined into NODE. */
3886 estimate_size_after_inlining (struct cgraph_node
*node
,
3887 struct cgraph_edge
*edge
)
3889 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3890 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3892 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3893 gcc_assert (size
>= 0);
3896 return inline_summaries
->get (node
)->size
;
3902 struct cgraph_node
*node
;
3903 bool self_recursive
;
3909 /* Worker for do_estimate_growth. Collect growth for all callers. */
3912 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3914 struct cgraph_edge
*e
;
3915 struct growth_data
*d
= (struct growth_data
*) data
;
3917 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3919 gcc_checking_assert (e
->inline_failed
);
3921 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3923 d
->uninlinable
= true;
3927 if (e
->caller
== d
->node
3928 || (e
->caller
->global
.inlined_to
3929 && e
->caller
->global
.inlined_to
== d
->node
))
3930 d
->self_recursive
= true;
3931 d
->growth
+= estimate_edge_growth (e
);
3937 /* Estimate the growth caused by inlining NODE into all callees. */
3940 estimate_growth (struct cgraph_node
*node
)
3942 struct growth_data d
= { node
, false, false, 0 };
3943 struct inline_summary
*info
= inline_summaries
->get (node
);
3945 node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true);
3947 /* For self recursive functions the growth estimation really should be
3948 infinity. We don't want to return very large values because the growth
3949 plays various roles in badness computation fractions. Be sure to not
3950 return zero or negative growths. */
3951 if (d
.self_recursive
)
3952 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3953 else if (DECL_EXTERNAL (node
->decl
) || d
.uninlinable
)
3957 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3958 d
.growth
-= info
->size
;
3959 /* COMDAT functions are very often not shared across multiple units
3960 since they come from various template instantiations.
3961 Take this into account. */
3962 else if (DECL_COMDAT (node
->decl
)
3963 && node
->can_remove_if_no_direct_calls_p ())
3964 d
.growth
-= (info
->size
3965 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3972 /* Verify if there are fewer than MAX_CALLERS. */
3975 check_callers (cgraph_node
*node
, int *max_callers
)
3979 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
3983 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3987 FOR_EACH_ALIAS (node
, ref
)
3988 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), max_callers
))
3995 /* Make cheap estimation if growth of NODE is likely positive knowing
3996 EDGE_GROWTH of one particular edge.
3997 We assume that most of other edges will have similar growth
3998 and skip computation if there are too many callers. */
4001 growth_likely_positive (struct cgraph_node
*node
,
4005 struct cgraph_edge
*e
;
4006 gcc_checking_assert (edge_growth
> 0);
4008 /* Unlike for functions called once, we play unsafe with
4009 COMDATs. We can allow that since we know functions
4010 in consideration are small (and thus risk is small) and
4011 moreover grow estimates already accounts that COMDAT
4012 functions may or may not disappear when eliminated from
4013 current unit. With good probability making aggressive
4014 choice in all units is going to make overall program
4017 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
4019 cgraph_will_be_removed_from_program_if_no_direct_calls */
4020 if (DECL_EXTERNAL (node
->decl
)
4021 || !node
->can_remove_if_no_direct_calls_p ())
4024 if (!node
->will_be_removed_from_program_if_no_direct_calls_p ()
4025 && (!DECL_COMDAT (node
->decl
)
4026 || !node
->can_remove_if_no_direct_calls_p ()))
4028 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
4030 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4034 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4039 FOR_EACH_ALIAS (node
, ref
)
4040 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), &max_callers
))
4043 return estimate_growth (node
) > 0;
4047 /* This function performs intraprocedural analysis in NODE that is required to
4048 inline indirect calls. */
4051 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4053 ipa_analyze_node (node
);
4054 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4056 ipa_print_node_params (dump_file
, node
);
4057 ipa_print_node_jump_functions (dump_file
, node
);
4062 /* Note function body size. */
4065 inline_analyze_function (struct cgraph_node
*node
)
4067 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4070 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4071 node
->name (), node
->order
);
4072 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4073 inline_indirect_intraprocedural_analysis (node
);
4074 compute_inline_parameters (node
, false);
4077 struct cgraph_edge
*e
;
4078 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4080 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4081 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4082 e
->call_stmt_cannot_inline_p
= true;
4084 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4086 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4087 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4088 e
->call_stmt_cannot_inline_p
= true;
4096 /* Called when new function is inserted to callgraph late. */
4099 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4101 inline_analyze_function (node
);
4104 /* Note function body size. */
4107 inline_generate_summary (void)
4109 struct cgraph_node
*node
;
4111 /* When not optimizing, do not bother to analyze. Inlining is still done
4112 because edge redirection needs to happen there. */
4113 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4116 if (!inline_summaries
)
4117 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4119 inline_summaries
->enable_insertion_hook ();
4121 ipa_register_cgraph_hooks ();
4122 inline_free_summary ();
4124 FOR_EACH_DEFINED_FUNCTION (node
)
4126 inline_analyze_function (node
);
4130 /* Read predicate from IB. */
4132 static struct predicate
4133 read_predicate (struct lto_input_block
*ib
)
4135 struct predicate out
;
4141 gcc_assert (k
<= MAX_CLAUSES
);
4142 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4146 /* Zero-initialize the remaining clauses in OUT. */
4147 while (k
<= MAX_CLAUSES
)
4148 out
.clause
[k
++] = 0;
4154 /* Write inline summary for edge E to OB. */
4157 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4159 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4163 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4164 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4165 es
->loop_depth
= streamer_read_uhwi (ib
);
4166 p
= read_predicate (ib
);
4167 edge_set_predicate (e
, &p
);
4168 length
= streamer_read_uhwi (ib
);
4171 es
->param
.safe_grow_cleared (length
);
4172 for (i
= 0; i
< length
; i
++)
4173 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4178 /* Stream in inline summaries from the section. */
4181 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4184 const struct lto_function_header
*header
=
4185 (const struct lto_function_header
*) data
;
4186 const int cfg_offset
= sizeof (struct lto_function_header
);
4187 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4188 const int string_offset
= main_offset
+ header
->main_size
;
4189 struct data_in
*data_in
;
4190 unsigned int i
, count2
, j
;
4191 unsigned int f_count
;
4193 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
);
4196 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4197 header
->string_size
, vNULL
);
4198 f_count
= streamer_read_uhwi (&ib
);
4199 for (i
= 0; i
< f_count
; i
++)
4202 struct cgraph_node
*node
;
4203 struct inline_summary
*info
;
4204 lto_symtab_encoder_t encoder
;
4205 struct bitpack_d bp
;
4206 struct cgraph_edge
*e
;
4209 index
= streamer_read_uhwi (&ib
);
4210 encoder
= file_data
->symtab_node_encoder
;
4211 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4213 info
= inline_summaries
->get (node
);
4215 info
->estimated_stack_size
4216 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4217 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4218 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4220 bp
= streamer_read_bitpack (&ib
);
4221 info
->inlinable
= bp_unpack_value (&bp
, 1);
4223 count2
= streamer_read_uhwi (&ib
);
4224 gcc_assert (!info
->conds
);
4225 for (j
= 0; j
< count2
; j
++)
4228 c
.operand_num
= streamer_read_uhwi (&ib
);
4229 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4230 c
.val
= stream_read_tree (&ib
, data_in
);
4231 bp
= streamer_read_bitpack (&ib
);
4232 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4233 c
.by_ref
= bp_unpack_value (&bp
, 1);
4235 c
.offset
= streamer_read_uhwi (&ib
);
4236 vec_safe_push (info
->conds
, c
);
4238 count2
= streamer_read_uhwi (&ib
);
4239 gcc_assert (!info
->entry
);
4240 for (j
= 0; j
< count2
; j
++)
4242 struct size_time_entry e
;
4244 e
.size
= streamer_read_uhwi (&ib
);
4245 e
.time
= streamer_read_uhwi (&ib
);
4246 e
.predicate
= read_predicate (&ib
);
4248 vec_safe_push (info
->entry
, e
);
4251 p
= read_predicate (&ib
);
4252 set_hint_predicate (&info
->loop_iterations
, p
);
4253 p
= read_predicate (&ib
);
4254 set_hint_predicate (&info
->loop_stride
, p
);
4255 p
= read_predicate (&ib
);
4256 set_hint_predicate (&info
->array_index
, p
);
4257 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4258 read_inline_edge_summary (&ib
, e
);
4259 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4260 read_inline_edge_summary (&ib
, e
);
4263 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4265 lto_data_in_delete (data_in
);
4269 /* Read inline summary. Jump functions are shared among ipa-cp
4270 and inliner, so when ipa-cp is active, we don't need to write them
4274 inline_read_summary (void)
4276 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4277 struct lto_file_decl_data
*file_data
;
4280 inline_summary_alloc ();
4282 while ((file_data
= file_data_vec
[j
++]))
4285 const char *data
= lto_get_section_data (file_data
,
4286 LTO_section_inline_summary
,
4289 inline_read_section (file_data
, data
, len
);
4291 /* Fatal error here. We do not want to support compiling ltrans units
4292 with different version of compiler or different flags than the WPA
4293 unit, so this should never happen. */
4294 fatal_error (input_location
,
4295 "ipa inline summary is missing in input file");
4299 ipa_register_cgraph_hooks ();
4301 ipa_prop_read_jump_functions ();
4304 gcc_assert (inline_summaries
);
4305 inline_summaries
->enable_insertion_hook ();
4309 /* Write predicate P to OB. */
4312 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4316 for (j
= 0; p
->clause
[j
]; j
++)
4318 gcc_assert (j
< MAX_CLAUSES
);
4319 streamer_write_uhwi (ob
, p
->clause
[j
]);
4321 streamer_write_uhwi (ob
, 0);
4325 /* Write inline summary for edge E to OB. */
4328 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4330 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4333 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4334 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4335 streamer_write_uhwi (ob
, es
->loop_depth
);
4336 write_predicate (ob
, es
->predicate
);
4337 streamer_write_uhwi (ob
, es
->param
.length ());
4338 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4339 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4343 /* Write inline summary for node in SET.
4344 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4345 active, we don't need to write them twice. */
4348 inline_write_summary (void)
4350 struct cgraph_node
*node
;
4351 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4352 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4353 unsigned int count
= 0;
4356 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4358 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4359 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4360 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4363 streamer_write_uhwi (ob
, count
);
4365 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4367 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4368 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4369 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4371 struct inline_summary
*info
= inline_summaries
->get (node
);
4372 struct bitpack_d bp
;
4373 struct cgraph_edge
*edge
;
4376 struct condition
*c
;
4378 streamer_write_uhwi (ob
,
4379 lto_symtab_encoder_encode (encoder
,
4382 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4383 streamer_write_hwi (ob
, info
->self_size
);
4384 streamer_write_hwi (ob
, info
->self_time
);
4385 bp
= bitpack_create (ob
->main_stream
);
4386 bp_pack_value (&bp
, info
->inlinable
, 1);
4387 streamer_write_bitpack (&bp
);
4388 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4389 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4391 streamer_write_uhwi (ob
, c
->operand_num
);
4392 streamer_write_uhwi (ob
, c
->code
);
4393 stream_write_tree (ob
, c
->val
, true);
4394 bp
= bitpack_create (ob
->main_stream
);
4395 bp_pack_value (&bp
, c
->agg_contents
, 1);
4396 bp_pack_value (&bp
, c
->by_ref
, 1);
4397 streamer_write_bitpack (&bp
);
4398 if (c
->agg_contents
)
4399 streamer_write_uhwi (ob
, c
->offset
);
4401 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4402 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4404 streamer_write_uhwi (ob
, e
->size
);
4405 streamer_write_uhwi (ob
, e
->time
);
4406 write_predicate (ob
, &e
->predicate
);
4408 write_predicate (ob
, info
->loop_iterations
);
4409 write_predicate (ob
, info
->loop_stride
);
4410 write_predicate (ob
, info
->array_index
);
4411 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4412 write_inline_edge_summary (ob
, edge
);
4413 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4414 write_inline_edge_summary (ob
, edge
);
4417 streamer_write_char_stream (ob
->main_stream
, 0);
4418 produce_asm (ob
, NULL
);
4419 destroy_output_block (ob
);
4421 if (optimize
&& !flag_ipa_cp
)
4422 ipa_prop_write_jump_functions ();
4426 /* Release inline summary. */
4429 inline_free_summary (void)
4431 struct cgraph_node
*node
;
4432 if (edge_removal_hook_holder
)
4433 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4434 edge_removal_hook_holder
= NULL
;
4435 if (edge_duplication_hook_holder
)
4436 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4437 edge_duplication_hook_holder
= NULL
;
4438 if (!inline_edge_summary_vec
.exists ())
4440 FOR_EACH_DEFINED_FUNCTION (node
)
4442 reset_inline_summary (node
, inline_summaries
->get (node
));
4443 inline_summaries
->release ();
4444 inline_summaries
= NULL
;
4445 inline_edge_summary_vec
.release ();
4446 if (edge_predicate_pool
)
4447 free_alloc_pool (edge_predicate_pool
);
4448 edge_predicate_pool
= 0;