1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Analysis used by the inliner and other passes limiting code size growth.
23 We estimate for each function
25 - average function execution time
26 - inlining size benefit (that is how much of function body size
27 and its call sequence is expected to disappear by inlining)
28 - inlining time benefit
31 - call statement size and time
33 inlinie_summary datastructures store above information locally (i.e.
34 parameters of the function itself) and globally (i.e. parameters of
35 the function created by applying all the inline decisions already
36 present in the callgraph).
38 We provide accestor to the inline_summary datastructure and
39 basic logic updating the parameters when inlining is performed.
41 The summaries are context sensitive. Context means
42 1) partial assignment of known constant values of operands
43 2) whether function is inlined into the call or not.
44 It is easy to add more variants. To represent function size and time
45 that depends on context (i.e. it is known to be optimized away when
46 context is known either by inlining or from IP-CP and clonning),
47 we use predicates. Predicates are logical formulas in
48 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
49 specifying what conditions must be true. Conditions are simple test
50 of the form described above.
52 In order to make predicate (possibly) true, all of its clauses must
53 be (possibly) true. To make clause (possibly) true, one of conditions
54 it mentions must be (possibly) true. There are fixed bounds on
55 number of clauses and conditions and all the manipulation functions
56 are conservative in positive direction. I.e. we may lose precision
57 by thinking that predicate may be true even when it is not.
59 estimate_edge_size and estimate_edge_growth can be used to query
60 function size/time in the given context. inline_merge_summary merges
61 properties of caller and callee after inlining.
63 Finally pass_inline_parameters is exported. This is used to drive
64 computation of function parameters used by the early inliner. IPA
65 inlined performs analysis via its analyze_function method. */
69 #include "coretypes.h"
72 #include "stor-layout.h"
73 #include "stringpool.h"
74 #include "print-tree.h"
75 #include "tree-inline.h"
76 #include "langhooks.h"
78 #include "diagnostic.h"
79 #include "gimple-pretty-print.h"
81 #include "tree-pass.h"
88 #include "hard-reg-set.h"
91 #include "dominance.h"
94 #include "basic-block.h"
95 #include "tree-ssa-alias.h"
96 #include "internal-fn.h"
97 #include "gimple-expr.h"
100 #include "gimple-iterator.h"
101 #include "gimple-ssa.h"
102 #include "tree-cfg.h"
103 #include "tree-phinodes.h"
104 #include "ssa-iterators.h"
105 #include "tree-ssanames.h"
106 #include "tree-ssa-loop-niter.h"
107 #include "tree-ssa-loop.h"
108 #include "hash-map.h"
109 #include "plugin-api.h"
112 #include "alloc-pool.h"
113 #include "ipa-prop.h"
114 #include "lto-streamer.h"
115 #include "data-streamer.h"
116 #include "tree-streamer.h"
117 #include "ipa-inline.h"
119 #include "tree-scalar-evolution.h"
120 #include "ipa-utils.h"
122 #include "cfgexpand.h"
124 /* Estimate runtime of function can easilly run into huge numbers with many
125 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
126 integer. For anything larger we use gcov_type. */
127 #define MAX_TIME 500000
129 /* Number of bits in integer, but we really want to be stable across different
131 #define NUM_CONDITIONS 32
133 enum predicate_conditions
135 predicate_false_condition
= 0,
136 predicate_not_inlined_condition
= 1,
137 predicate_first_dynamic_condition
= 2
140 /* Special condition code we use to represent test that operand is compile time
142 #define IS_NOT_CONSTANT ERROR_MARK
143 /* Special condition code we use to represent test that operand is not changed
144 across invocation of the function. When operand IS_NOT_CONSTANT it is always
145 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
146 of executions even when they are not compile time constants. */
147 #define CHANGED IDENTIFIER_NODE
149 /* Holders of ipa cgraph hooks: */
150 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
151 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
152 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
153 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
154 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
155 static void inline_node_removal_hook (struct cgraph_node
*, void *);
156 static void inline_node_duplication_hook (struct cgraph_node
*,
157 struct cgraph_node
*, void *);
158 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
159 static void inline_edge_duplication_hook (struct cgraph_edge
*,
160 struct cgraph_edge
*, void *);
162 /* VECtor holding inline summaries.
163 In GGC memory because conditions might point to constant trees. */
164 vec
<inline_summary_t
, va_gc
> *inline_summary_vec
;
165 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
167 /* Cached node/edge growths. */
168 vec
<int> node_growth_cache
;
169 vec
<edge_growth_cache_entry
> edge_growth_cache
;
171 /* Edge predicates goes here. */
172 static alloc_pool edge_predicate_pool
;
174 /* Return true predicate (tautology).
175 We represent it by empty list of clauses. */
177 static inline struct predicate
178 true_predicate (void)
186 /* Return predicate testing single condition number COND. */
188 static inline struct predicate
189 single_cond_predicate (int cond
)
192 p
.clause
[0] = 1 << cond
;
198 /* Return false predicate. First clause require false condition. */
200 static inline struct predicate
201 false_predicate (void)
203 return single_cond_predicate (predicate_false_condition
);
207 /* Return true if P is (true). */
210 true_predicate_p (struct predicate
*p
)
212 return !p
->clause
[0];
216 /* Return true if P is (false). */
219 false_predicate_p (struct predicate
*p
)
221 if (p
->clause
[0] == (1 << predicate_false_condition
))
223 gcc_checking_assert (!p
->clause
[1]
224 && p
->clause
[0] == 1 << predicate_false_condition
);
231 /* Return predicate that is set true when function is not inlined. */
233 static inline struct predicate
234 not_inlined_predicate (void)
236 return single_cond_predicate (predicate_not_inlined_condition
);
239 /* Simple description of whether a memory load or a condition refers to a load
240 from an aggregate and if so, how and where from in the aggregate.
241 Individual fields have the same meaning like fields with the same name in
244 struct agg_position_info
246 HOST_WIDE_INT offset
;
251 /* Add condition to condition list CONDS. AGGPOS describes whether the used
252 oprand is loaded from an aggregate and where in the aggregate it is. It can
253 be NULL, which means this not a load from an aggregate. */
255 static struct predicate
256 add_condition (struct inline_summary
*summary
, int operand_num
,
257 struct agg_position_info
*aggpos
,
258 enum tree_code code
, tree val
)
262 struct condition new_cond
;
263 HOST_WIDE_INT offset
;
264 bool agg_contents
, by_ref
;
268 offset
= aggpos
->offset
;
269 agg_contents
= aggpos
->agg_contents
;
270 by_ref
= aggpos
->by_ref
;
275 agg_contents
= false;
279 gcc_checking_assert (operand_num
>= 0);
280 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
282 if (c
->operand_num
== operand_num
285 && c
->agg_contents
== agg_contents
286 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
287 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
289 /* Too many conditions. Give up and return constant true. */
290 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
291 return true_predicate ();
293 new_cond
.operand_num
= operand_num
;
294 new_cond
.code
= code
;
296 new_cond
.agg_contents
= agg_contents
;
297 new_cond
.by_ref
= by_ref
;
298 new_cond
.offset
= offset
;
299 vec_safe_push (summary
->conds
, new_cond
);
300 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
304 /* Add clause CLAUSE into the predicate P. */
307 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
311 int insert_here
= -1;
318 /* False clause makes the whole predicate false. Kill the other variants. */
319 if (clause
== (1 << predicate_false_condition
))
321 p
->clause
[0] = (1 << predicate_false_condition
);
325 if (false_predicate_p (p
))
328 /* No one should be silly enough to add false into nontrivial clauses. */
329 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
331 /* Look where to insert the clause. At the same time prune out
332 clauses of P that are implied by the new clause and thus
334 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
336 p
->clause
[i2
] = p
->clause
[i
];
341 /* If p->clause[i] implies clause, there is nothing to add. */
342 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
344 /* We had nothing to add, none of clauses should've become
346 gcc_checking_assert (i
== i2
);
350 if (p
->clause
[i
] < clause
&& insert_here
< 0)
353 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
354 Otherwise the p->clause[i] has to stay. */
355 if ((p
->clause
[i
] & clause
) != clause
)
359 /* Look for clauses that are obviously true. I.e.
360 op0 == 5 || op0 != 5. */
361 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
364 if (!(clause
& (1 << c1
)))
366 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
367 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
368 and thus there is no point for looking for them. */
369 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
371 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
372 if (clause
& (1 << c2
))
375 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
377 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
378 if (cc1
->operand_num
== cc2
->operand_num
379 && cc1
->val
== cc2
->val
380 && cc2
->code
!= IS_NOT_CONSTANT
381 && cc2
->code
!= CHANGED
382 && cc1
->code
== invert_tree_comparison
384 HONOR_NANS (TYPE_MODE (TREE_TYPE (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
;
780 callee
->remove_symbol_and_inline_clones ();
782 if (predicate
&& !true_predicate_p (predicate
))
785 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
786 *es
->predicate
= *predicate
;
791 pool_free (edge_predicate_pool
, es
->predicate
);
792 es
->predicate
= NULL
;
796 /* Set predicate for hint *P. */
799 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
801 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
804 pool_free (edge_predicate_pool
, *p
);
810 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
816 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
817 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
818 Return clause of possible truths. When INLINE_P is true, assume that we are
821 ERROR_MARK means compile time invariant. */
824 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
826 vec
<tree
> known_vals
,
827 vec
<ipa_agg_jump_function_p
>
830 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
831 struct inline_summary
*info
= inline_summary (node
);
835 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
840 /* We allow call stmt to have fewer arguments than the callee function
841 (especially for K&R style programs). So bound check here (we assume
842 known_aggs vector, if non-NULL, has the same length as
844 gcc_checking_assert (!known_aggs
.exists ()
845 || (known_vals
.length () == known_aggs
.length ()));
846 if (c
->operand_num
>= (int) known_vals
.length ())
848 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
854 struct ipa_agg_jump_function
*agg
;
856 if (c
->code
== CHANGED
858 && (known_vals
[c
->operand_num
] == error_mark_node
))
861 if (known_aggs
.exists ())
863 agg
= known_aggs
[c
->operand_num
];
864 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
871 val
= known_vals
[c
->operand_num
];
872 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
878 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
881 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
883 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
885 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
887 if (res
&& integer_zerop (res
))
889 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
895 /* Work out what conditions might be true at invocation of E. */
898 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
899 clause_t
*clause_ptr
,
900 vec
<tree
> *known_vals_ptr
,
901 vec
<ipa_polymorphic_call_context
>
903 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
905 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
906 struct inline_summary
*info
= inline_summary (callee
);
907 vec
<tree
> known_vals
= vNULL
;
908 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
911 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
913 known_vals_ptr
->create (0);
914 if (known_contexts_ptr
)
915 known_contexts_ptr
->create (0);
917 if (ipa_node_params_vector
.exists ()
918 && !e
->call_stmt_cannot_inline_p
919 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
921 struct ipa_node_params
*parms_info
;
922 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
923 struct inline_edge_summary
*es
= inline_edge_summary (e
);
924 int i
, count
= ipa_get_cs_argument_count (args
);
926 if (e
->caller
->global
.inlined_to
)
927 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
929 parms_info
= IPA_NODE_REF (e
->caller
);
931 if (count
&& (info
->conds
|| known_vals_ptr
))
932 known_vals
.safe_grow_cleared (count
);
933 if (count
&& (info
->conds
|| known_aggs_ptr
))
934 known_aggs
.safe_grow_cleared (count
);
935 if (count
&& known_contexts_ptr
)
936 known_contexts_ptr
->safe_grow_cleared (count
);
938 for (i
= 0; i
< count
; i
++)
940 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
941 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
944 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
945 if (known_vals
.exists ())
948 else if (inline_p
&& !es
->param
[i
].change_prob
)
949 known_vals
[i
] = error_mark_node
;
951 if (known_contexts_ptr
)
952 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
954 /* TODO: When IPA-CP starts propagating and merging aggregate jump
955 functions, use its knowledge of the caller too, just like the
956 scalar case above. */
957 known_aggs
[i
] = &jf
->agg
;
962 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
963 known_vals
, known_aggs
);
966 *known_vals_ptr
= known_vals
;
968 known_vals
.release ();
971 *known_aggs_ptr
= known_aggs
;
973 known_aggs
.release ();
977 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
980 inline_summary_alloc (void)
982 if (!node_removal_hook_holder
)
983 node_removal_hook_holder
=
984 symtab
->add_cgraph_removal_hook (&inline_node_removal_hook
, NULL
);
985 if (!edge_removal_hook_holder
)
986 edge_removal_hook_holder
=
987 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
988 if (!node_duplication_hook_holder
)
989 node_duplication_hook_holder
=
990 symtab
->add_cgraph_duplication_hook (&inline_node_duplication_hook
, NULL
);
991 if (!edge_duplication_hook_holder
)
992 edge_duplication_hook_holder
=
993 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
995 if (vec_safe_length (inline_summary_vec
) <= (unsigned) symtab
->cgraph_max_uid
)
996 vec_safe_grow_cleared (inline_summary_vec
, symtab
->cgraph_max_uid
+ 1);
997 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
998 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
999 if (!edge_predicate_pool
)
1000 edge_predicate_pool
= create_alloc_pool ("edge predicates",
1001 sizeof (struct predicate
), 10);
1004 /* We are called multiple time for given function; clear
1005 data from previous run so they are not cumulated. */
1008 reset_inline_edge_summary (struct cgraph_edge
*e
)
1010 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1012 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1014 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1016 pool_free (edge_predicate_pool
, es
->predicate
);
1017 es
->predicate
= NULL
;
1018 es
->param
.release ();
1022 /* We are called multiple time for given function; clear
1023 data from previous run so they are not cumulated. */
1026 reset_inline_summary (struct cgraph_node
*node
)
1028 struct inline_summary
*info
= inline_summary (node
);
1029 struct cgraph_edge
*e
;
1031 info
->self_size
= info
->self_time
= 0;
1032 info
->estimated_stack_size
= 0;
1033 info
->estimated_self_stack_size
= 0;
1034 info
->stack_frame_offset
= 0;
1039 if (info
->loop_iterations
)
1041 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1042 info
->loop_iterations
= NULL
;
1044 if (info
->loop_stride
)
1046 pool_free (edge_predicate_pool
, info
->loop_stride
);
1047 info
->loop_stride
= NULL
;
1049 if (info
->array_index
)
1051 pool_free (edge_predicate_pool
, info
->array_index
);
1052 info
->array_index
= NULL
;
1054 vec_free (info
->conds
);
1055 vec_free (info
->entry
);
1056 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1057 reset_inline_edge_summary (e
);
1058 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1059 reset_inline_edge_summary (e
);
1062 /* Hook that is called by cgraph.c when a node is removed. */
1065 inline_node_removal_hook (struct cgraph_node
*node
,
1066 void *data ATTRIBUTE_UNUSED
)
1068 struct inline_summary
*info
;
1069 if (vec_safe_length (inline_summary_vec
) <= (unsigned) node
->uid
)
1071 info
= inline_summary (node
);
1072 reset_inline_summary (node
);
1073 memset (info
, 0, sizeof (inline_summary_t
));
1076 /* Remap predicate P of former function to be predicate of duplicated function.
1077 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1078 INFO is inline summary of the duplicated node. */
1080 static struct predicate
1081 remap_predicate_after_duplication (struct predicate
*p
,
1082 clause_t possible_truths
,
1083 struct inline_summary
*info
)
1085 struct predicate new_predicate
= true_predicate ();
1087 for (j
= 0; p
->clause
[j
]; j
++)
1088 if (!(possible_truths
& p
->clause
[j
]))
1090 new_predicate
= false_predicate ();
1094 add_clause (info
->conds
, &new_predicate
,
1095 possible_truths
& p
->clause
[j
]);
1096 return new_predicate
;
1099 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1100 Additionally care about allocating new memory slot for updated predicate
1101 and set it to NULL when it becomes true or false (and thus uninteresting).
1105 remap_hint_predicate_after_duplication (struct predicate
**p
,
1106 clause_t possible_truths
,
1107 struct inline_summary
*info
)
1109 struct predicate new_predicate
;
1114 new_predicate
= remap_predicate_after_duplication (*p
,
1115 possible_truths
, info
);
1116 /* We do not want to free previous predicate; it is used by node origin. */
1118 set_hint_predicate (p
, new_predicate
);
1122 /* Hook that is called by cgraph.c when a node is duplicated. */
1125 inline_node_duplication_hook (struct cgraph_node
*src
,
1126 struct cgraph_node
*dst
,
1127 ATTRIBUTE_UNUSED
void *data
)
1129 struct inline_summary
*info
;
1130 inline_summary_alloc ();
1131 info
= inline_summary (dst
);
1132 memcpy (info
, inline_summary (src
), sizeof (struct inline_summary
));
1133 /* TODO: as an optimization, we may avoid copying conditions
1134 that are known to be false or true. */
1135 info
->conds
= vec_safe_copy (info
->conds
);
1137 /* When there are any replacements in the function body, see if we can figure
1138 out that something was optimized out. */
1139 if (ipa_node_params_vector
.exists () && dst
->clone
.tree_map
)
1141 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1142 /* Use SRC parm info since it may not be copied yet. */
1143 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1144 vec
<tree
> known_vals
= vNULL
;
1145 int count
= ipa_get_param_count (parms_info
);
1147 clause_t possible_truths
;
1148 struct predicate true_pred
= true_predicate ();
1150 int optimized_out_size
= 0;
1151 bool inlined_to_p
= false;
1152 struct cgraph_edge
*edge
;
1155 known_vals
.safe_grow_cleared (count
);
1156 for (i
= 0; i
< count
; i
++)
1158 struct ipa_replace_map
*r
;
1160 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1162 if (((!r
->old_tree
&& r
->parm_num
== i
)
1163 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1164 && r
->replace_p
&& !r
->ref_p
)
1166 known_vals
[i
] = r
->new_tree
;
1171 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1174 known_vals
.release ();
1176 account_size_time (info
, 0, 0, &true_pred
);
1178 /* Remap size_time vectors.
1179 Simplify the predicate by prunning out alternatives that are known
1181 TODO: as on optimization, we can also eliminate conditions known
1183 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1185 struct predicate new_predicate
;
1186 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1189 if (false_predicate_p (&new_predicate
))
1190 optimized_out_size
+= e
->size
;
1192 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1195 /* Remap edge predicates with the same simplification as above.
1196 Also copy constantness arrays. */
1197 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1199 struct predicate new_predicate
;
1200 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1202 if (!edge
->inline_failed
)
1203 inlined_to_p
= true;
1206 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1209 if (false_predicate_p (&new_predicate
)
1210 && !false_predicate_p (es
->predicate
))
1212 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1213 edge
->frequency
= 0;
1215 edge_set_predicate (edge
, &new_predicate
);
1218 /* Remap indirect edge predicates with the same simplificaiton as above.
1219 Also copy constantness arrays. */
1220 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1222 struct predicate new_predicate
;
1223 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1225 gcc_checking_assert (edge
->inline_failed
);
1228 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1231 if (false_predicate_p (&new_predicate
)
1232 && !false_predicate_p (es
->predicate
))
1234 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1235 edge
->frequency
= 0;
1237 edge_set_predicate (edge
, &new_predicate
);
1239 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1240 possible_truths
, info
);
1241 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1242 possible_truths
, info
);
1243 remap_hint_predicate_after_duplication (&info
->array_index
,
1244 possible_truths
, info
);
1246 /* If inliner or someone after inliner will ever start producing
1247 non-trivial clones, we will get trouble with lack of information
1248 about updating self sizes, because size vectors already contains
1249 sizes of the calees. */
1250 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1254 info
->entry
= vec_safe_copy (info
->entry
);
1255 if (info
->loop_iterations
)
1257 predicate p
= *info
->loop_iterations
;
1258 info
->loop_iterations
= NULL
;
1259 set_hint_predicate (&info
->loop_iterations
, p
);
1261 if (info
->loop_stride
)
1263 predicate p
= *info
->loop_stride
;
1264 info
->loop_stride
= NULL
;
1265 set_hint_predicate (&info
->loop_stride
, p
);
1267 if (info
->array_index
)
1269 predicate p
= *info
->array_index
;
1270 info
->array_index
= NULL
;
1271 set_hint_predicate (&info
->array_index
, p
);
1274 inline_update_overall_summary (dst
);
1278 /* Hook that is called by cgraph.c when a node is duplicated. */
1281 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1282 struct cgraph_edge
*dst
,
1283 ATTRIBUTE_UNUSED
void *data
)
1285 struct inline_edge_summary
*info
;
1286 struct inline_edge_summary
*srcinfo
;
1287 inline_summary_alloc ();
1288 info
= inline_edge_summary (dst
);
1289 srcinfo
= inline_edge_summary (src
);
1290 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1291 info
->predicate
= NULL
;
1292 edge_set_predicate (dst
, srcinfo
->predicate
);
1293 info
->param
= srcinfo
->param
.copy ();
1297 /* Keep edge cache consistent across edge removal. */
1300 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1301 void *data ATTRIBUTE_UNUSED
)
1303 if (edge_growth_cache
.exists ())
1304 reset_edge_growth_cache (edge
);
1305 reset_inline_edge_summary (edge
);
1309 /* Initialize growth caches. */
1312 initialize_growth_caches (void)
1314 if (symtab
->edges_max_uid
)
1315 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1316 if (symtab
->cgraph_max_uid
)
1317 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
1321 /* Free growth caches. */
1324 free_growth_caches (void)
1326 edge_growth_cache
.release ();
1327 node_growth_cache
.release ();
1331 /* Dump edge summaries associated to NODE and recursively to all clones.
1332 Indent by INDENT. */
1335 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1336 struct inline_summary
*info
)
1338 struct cgraph_edge
*edge
;
1339 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1341 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1342 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1346 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1347 " time: %2i callee size:%2i stack:%2i",
1348 indent
, "", callee
->name (), callee
->order
,
1349 !edge
->inline_failed
1350 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1351 indent
, "", es
->loop_depth
, edge
->frequency
,
1352 es
->call_stmt_size
, es
->call_stmt_time
,
1353 (int) inline_summary (callee
)->size
/ INLINE_SIZE_SCALE
,
1354 (int) inline_summary (callee
)->estimated_stack_size
);
1358 fprintf (f
, " predicate: ");
1359 dump_predicate (f
, info
->conds
, es
->predicate
);
1363 if (es
->param
.exists ())
1364 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1366 int prob
= es
->param
[i
].change_prob
;
1369 fprintf (f
, "%*s op%i is compile time invariant\n",
1371 else if (prob
!= REG_BR_PROB_BASE
)
1372 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1373 prob
* 100.0 / REG_BR_PROB_BASE
);
1375 if (!edge
->inline_failed
)
1377 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1378 " callee size %i\n",
1380 (int) inline_summary (callee
)->stack_frame_offset
,
1381 (int) inline_summary (callee
)->estimated_self_stack_size
,
1382 (int) inline_summary (callee
)->estimated_stack_size
);
1383 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1386 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1388 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1389 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1393 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1396 fprintf (f
, "predicate: ");
1397 dump_predicate (f
, info
->conds
, es
->predicate
);
1406 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1408 if (node
->definition
)
1410 struct inline_summary
*s
= inline_summary (node
);
1413 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1415 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1416 fprintf (f
, " always_inline");
1418 fprintf (f
, " inlinable");
1419 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1420 fprintf (f
, " global time: %i\n", s
->time
);
1421 fprintf (f
, " self size: %i\n", s
->self_size
);
1422 fprintf (f
, " global size: %i\n", s
->size
);
1423 fprintf (f
, " min size: %i\n", s
->min_size
);
1424 fprintf (f
, " self stack: %i\n",
1425 (int) s
->estimated_self_stack_size
);
1426 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1428 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1430 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1431 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1433 fprintf (f
, " size:%f, time:%f, predicate:",
1434 (double) e
->size
/ INLINE_SIZE_SCALE
,
1435 (double) e
->time
/ INLINE_TIME_SCALE
);
1436 dump_predicate (f
, s
->conds
, &e
->predicate
);
1438 if (s
->loop_iterations
)
1440 fprintf (f
, " loop iterations:");
1441 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1445 fprintf (f
, " loop stride:");
1446 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1450 fprintf (f
, " array index:");
1451 dump_predicate (f
, s
->conds
, s
->array_index
);
1453 fprintf (f
, " calls:\n");
1454 dump_inline_edge_summary (f
, 4, node
, s
);
1460 debug_inline_summary (struct cgraph_node
*node
)
1462 dump_inline_summary (stderr
, node
);
1466 dump_inline_summaries (FILE *f
)
1468 struct cgraph_node
*node
;
1470 FOR_EACH_DEFINED_FUNCTION (node
)
1471 if (!node
->global
.inlined_to
)
1472 dump_inline_summary (f
, node
);
1475 /* Give initial reasons why inlining would fail on EDGE. This gets either
1476 nullified or usually overwritten by more precise reasons later. */
1479 initialize_inline_failed (struct cgraph_edge
*e
)
1481 struct cgraph_node
*callee
= e
->callee
;
1483 if (e
->indirect_unknown_callee
)
1484 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1485 else if (!callee
->definition
)
1486 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1487 else if (callee
->local
.redefined_extern_inline
)
1488 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1489 else if (e
->call_stmt_cannot_inline_p
)
1490 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1491 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1492 /* We can't inline if the function is spawing a function. */
1493 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1495 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1498 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1499 boolean variable pointed to by DATA. */
1502 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1505 bool *b
= (bool *) data
;
1510 /* If OP refers to value of function parameter, return the corresponding
1514 unmodified_parm_1 (gimple stmt
, tree op
)
1516 /* SSA_NAME referring to parm default def? */
1517 if (TREE_CODE (op
) == SSA_NAME
1518 && SSA_NAME_IS_DEFAULT_DEF (op
)
1519 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1520 return SSA_NAME_VAR (op
);
1521 /* Non-SSA parm reference? */
1522 if (TREE_CODE (op
) == PARM_DECL
)
1524 bool modified
= false;
1527 ao_ref_init (&refd
, op
);
1528 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1536 /* If OP refers to value of function parameter, return the corresponding
1537 parameter. Also traverse chains of SSA register assignments. */
1540 unmodified_parm (gimple stmt
, tree op
)
1542 tree res
= unmodified_parm_1 (stmt
, op
);
1546 if (TREE_CODE (op
) == SSA_NAME
1547 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1548 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1549 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1550 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1554 /* If OP refers to a value of a function parameter or value loaded from an
1555 aggregate passed to a parameter (either by value or reference), return TRUE
1556 and store the number of the parameter to *INDEX_P and information whether
1557 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1558 the function parameters, STMT is the statement in which OP is used or
1562 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1563 gimple stmt
, tree op
, int *index_p
,
1564 struct agg_position_info
*aggpos
)
1566 tree res
= unmodified_parm_1 (stmt
, op
);
1568 gcc_checking_assert (aggpos
);
1571 *index_p
= ipa_get_param_decl_index (info
, res
);
1574 aggpos
->agg_contents
= false;
1575 aggpos
->by_ref
= false;
1579 if (TREE_CODE (op
) == SSA_NAME
)
1581 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1582 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1584 stmt
= SSA_NAME_DEF_STMT (op
);
1585 op
= gimple_assign_rhs1 (stmt
);
1586 if (!REFERENCE_CLASS_P (op
))
1587 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1591 aggpos
->agg_contents
= true;
1592 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1596 /* See if statement might disappear after inlining.
1597 0 - means not eliminated
1598 1 - half of statements goes away
1599 2 - for sure it is eliminated.
1600 We are not terribly sophisticated, basically looking for simple abstraction
1601 penalty wrappers. */
1604 eliminated_by_inlining_prob (gimple stmt
)
1606 enum gimple_code code
= gimple_code (stmt
);
1607 enum tree_code rhs_code
;
1617 if (gimple_num_ops (stmt
) != 2)
1620 rhs_code
= gimple_assign_rhs_code (stmt
);
1622 /* Casts of parameters, loads from parameters passed by reference
1623 and stores to return value or parameters are often free after
1624 inlining dua to SRA and further combining.
1625 Assume that half of statements goes away. */
1626 if (CONVERT_EXPR_CODE_P (rhs_code
)
1627 || rhs_code
== VIEW_CONVERT_EXPR
1628 || rhs_code
== ADDR_EXPR
1629 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1631 tree rhs
= gimple_assign_rhs1 (stmt
);
1632 tree lhs
= gimple_assign_lhs (stmt
);
1633 tree inner_rhs
= get_base_address (rhs
);
1634 tree inner_lhs
= get_base_address (lhs
);
1635 bool rhs_free
= false;
1636 bool lhs_free
= false;
1643 /* Reads of parameter are expected to be free. */
1644 if (unmodified_parm (stmt
, inner_rhs
))
1646 /* Match expressions of form &this->field. Those will most likely
1647 combine with something upstream after inlining. */
1648 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1650 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1651 if (TREE_CODE (op
) == PARM_DECL
)
1653 else if (TREE_CODE (op
) == MEM_REF
1654 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1658 /* When parameter is not SSA register because its address is taken
1659 and it is just copied into one, the statement will be completely
1660 free after inlining (we will copy propagate backward). */
1661 if (rhs_free
&& is_gimple_reg (lhs
))
1664 /* Reads of parameters passed by reference
1665 expected to be free (i.e. optimized out after inlining). */
1666 if (TREE_CODE (inner_rhs
) == MEM_REF
1667 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1670 /* Copying parameter passed by reference into gimple register is
1671 probably also going to copy propagate, but we can't be quite
1673 if (rhs_free
&& is_gimple_reg (lhs
))
1676 /* Writes to parameters, parameters passed by value and return value
1677 (either dirrectly or passed via invisible reference) are free.
1679 TODO: We ought to handle testcase like
1680 struct a {int a,b;};
1682 retrurnsturct (void)
1688 This translate into:
1703 For that we either need to copy ipa-split logic detecting writes
1705 if (TREE_CODE (inner_lhs
) == PARM_DECL
1706 || TREE_CODE (inner_lhs
) == RESULT_DECL
1707 || (TREE_CODE (inner_lhs
) == MEM_REF
1708 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1709 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1710 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1711 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1713 0))) == RESULT_DECL
))))
1716 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1718 if (lhs_free
&& rhs_free
)
1728 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1729 predicates to the CFG edges. */
1732 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1733 struct inline_summary
*summary
,
1739 struct agg_position_info aggpos
;
1740 enum tree_code code
, inverted_code
;
1746 last
= last_stmt (bb
);
1747 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1749 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1751 op
= gimple_cond_lhs (last
);
1752 /* TODO: handle conditionals like
1755 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1757 code
= gimple_cond_code (last
);
1759 = invert_tree_comparison (code
,
1760 HONOR_NANS (TYPE_MODE (TREE_TYPE (op
))));
1762 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1764 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1765 ? code
: inverted_code
);
1766 /* invert_tree_comparison will return ERROR_MARK on FP
1767 comparsions that are not EQ/NE instead of returning proper
1768 unordered one. Be sure it is not confused with NON_CONSTANT. */
1769 if (this_code
!= ERROR_MARK
)
1771 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1773 gimple_cond_rhs (last
));
1774 e
->aux
= pool_alloc (edge_predicate_pool
);
1775 *(struct predicate
*) e
->aux
= p
;
1780 if (TREE_CODE (op
) != SSA_NAME
)
1783 if (builtin_constant_p (op))
1787 Here we can predicate nonconstant_code. We can't
1788 really handle constant_code since we have no predicate
1789 for this and also the constant code is not known to be
1790 optimized away when inliner doen't see operand is constant.
1791 Other optimizers might think otherwise. */
1792 if (gimple_cond_code (last
) != NE_EXPR
1793 || !integer_zerop (gimple_cond_rhs (last
)))
1795 set_stmt
= SSA_NAME_DEF_STMT (op
);
1796 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1797 || gimple_call_num_args (set_stmt
) != 1)
1799 op2
= gimple_call_arg (set_stmt
, 0);
1800 if (!unmodified_parm_or_parm_agg_item
1801 (info
, set_stmt
, op2
, &index
, &aggpos
))
1803 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1805 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1806 IS_NOT_CONSTANT
, NULL_TREE
);
1807 e
->aux
= pool_alloc (edge_predicate_pool
);
1808 *(struct predicate
*) e
->aux
= p
;
1813 /* If BB ends by a switch we can turn into predicates, attach corresponding
1814 predicates to the CFG edges. */
1817 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1818 struct inline_summary
*summary
,
1824 struct agg_position_info aggpos
;
1830 lastg
= last_stmt (bb
);
1831 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1833 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1834 op
= gimple_switch_index (last
);
1835 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1838 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1840 e
->aux
= pool_alloc (edge_predicate_pool
);
1841 *(struct predicate
*) e
->aux
= false_predicate ();
1843 n
= gimple_switch_num_labels (last
);
1844 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1846 tree cl
= gimple_switch_label (last
, case_idx
);
1850 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1851 min
= CASE_LOW (cl
);
1852 max
= CASE_HIGH (cl
);
1854 /* For default we might want to construct predicate that none
1855 of cases is met, but it is bit hard to do not having negations
1856 of conditionals handy. */
1858 p
= true_predicate ();
1860 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1863 struct predicate p1
, p2
;
1864 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1865 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1866 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1868 *(struct predicate
*) e
->aux
1869 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1874 /* For each BB in NODE attach to its AUX pointer predicate under
1875 which it is executable. */
1878 compute_bb_predicates (struct cgraph_node
*node
,
1879 struct ipa_node_params
*parms_info
,
1880 struct inline_summary
*summary
)
1882 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1886 FOR_EACH_BB_FN (bb
, my_function
)
1888 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1889 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1892 /* Entry block is always executable. */
1893 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1894 = pool_alloc (edge_predicate_pool
);
1895 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1896 = true_predicate ();
1898 /* A simple dataflow propagation of predicates forward in the CFG.
1899 TODO: work in reverse postorder. */
1903 FOR_EACH_BB_FN (bb
, my_function
)
1905 struct predicate p
= false_predicate ();
1908 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1912 struct predicate this_bb_predicate
1913 = *(struct predicate
*) e
->src
->aux
;
1916 = and_predicates (summary
->conds
, &this_bb_predicate
,
1917 (struct predicate
*) e
->aux
);
1918 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1919 if (true_predicate_p (&p
))
1923 if (false_predicate_p (&p
))
1924 gcc_assert (!bb
->aux
);
1930 bb
->aux
= pool_alloc (edge_predicate_pool
);
1931 *((struct predicate
*) bb
->aux
) = p
;
1933 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1935 /* This OR operation is needed to ensure monotonous data flow
1936 in the case we hit the limit on number of clauses and the
1937 and/or operations above give approximate answers. */
1938 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1939 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1942 *((struct predicate
*) bb
->aux
) = p
;
1951 /* We keep info about constantness of SSA names. */
1953 typedef struct predicate predicate_t
;
1954 /* Return predicate specifying when the STMT might have result that is not
1955 a compile time constant. */
1957 static struct predicate
1958 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1959 struct inline_summary
*summary
,
1961 vec
<predicate_t
> nonconstant_names
)
1966 while (UNARY_CLASS_P (expr
))
1967 expr
= TREE_OPERAND (expr
, 0);
1969 parm
= unmodified_parm (NULL
, expr
);
1970 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1971 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1972 if (is_gimple_min_invariant (expr
))
1973 return false_predicate ();
1974 if (TREE_CODE (expr
) == SSA_NAME
)
1975 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1976 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1978 struct predicate p1
= will_be_nonconstant_expr_predicate
1979 (info
, summary
, TREE_OPERAND (expr
, 0),
1981 struct predicate p2
;
1982 if (true_predicate_p (&p1
))
1984 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1985 TREE_OPERAND (expr
, 1),
1987 return or_predicates (summary
->conds
, &p1
, &p2
);
1989 else if (TREE_CODE (expr
) == COND_EXPR
)
1991 struct predicate p1
= will_be_nonconstant_expr_predicate
1992 (info
, summary
, TREE_OPERAND (expr
, 0),
1994 struct predicate p2
;
1995 if (true_predicate_p (&p1
))
1997 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1998 TREE_OPERAND (expr
, 1),
2000 if (true_predicate_p (&p2
))
2002 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2003 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2004 TREE_OPERAND (expr
, 2),
2006 return or_predicates (summary
->conds
, &p1
, &p2
);
2013 return false_predicate ();
2017 /* Return predicate specifying when the STMT might have result that is not
2018 a compile time constant. */
2020 static struct predicate
2021 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2022 struct inline_summary
*summary
,
2024 vec
<predicate_t
> nonconstant_names
)
2026 struct predicate p
= true_predicate ();
2029 struct predicate op_non_const
;
2032 struct agg_position_info aggpos
;
2034 /* What statments might be optimized away
2035 when their arguments are constant
2036 TODO: also trivial builtins.
2037 builtin_constant_p is already handled later. */
2038 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2039 && gimple_code (stmt
) != GIMPLE_COND
2040 && gimple_code (stmt
) != GIMPLE_SWITCH
)
2043 /* Stores will stay anyway. */
2044 if (gimple_store_p (stmt
))
2047 is_load
= gimple_assign_load_p (stmt
);
2049 /* Loads can be optimized when the value is known. */
2053 gcc_assert (gimple_assign_single_p (stmt
));
2054 op
= gimple_assign_rhs1 (stmt
);
2055 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2062 /* See if we understand all operands before we start
2063 adding conditionals. */
2064 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2066 tree parm
= unmodified_parm (stmt
, use
);
2067 /* For arguments we can build a condition. */
2068 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2070 if (TREE_CODE (use
) != SSA_NAME
)
2072 /* If we know when operand is constant,
2073 we still can say something useful. */
2074 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2081 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2083 op_non_const
= false_predicate ();
2084 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2086 tree parm
= unmodified_parm (stmt
, use
);
2089 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2091 if (index
!= base_index
)
2092 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2097 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2098 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2100 if (gimple_code (stmt
) == GIMPLE_ASSIGN
2101 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
)
2102 nonconstant_names
[SSA_NAME_VERSION (gimple_assign_lhs (stmt
))]
2104 return op_non_const
;
2107 struct record_modified_bb_info
2113 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2114 set except for info->stmt. */
2117 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2119 struct record_modified_bb_info
*info
=
2120 (struct record_modified_bb_info
*) data
;
2121 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2123 bitmap_set_bit (info
->bb_set
,
2124 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2125 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2126 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2130 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2131 will change since last invocation of STMT.
2133 Value 0 is reserved for compile time invariants.
2134 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2135 ought to be REG_BR_PROB_BASE / estimated_iters. */
2138 param_change_prob (gimple stmt
, int i
)
2140 tree op
= gimple_call_arg (stmt
, i
);
2141 basic_block bb
= gimple_bb (stmt
);
2144 /* Global invariants neve change. */
2145 if (is_gimple_min_invariant (op
))
2147 /* We would have to do non-trivial analysis to really work out what
2148 is the probability of value to change (i.e. when init statement
2149 is in a sibling loop of the call).
2151 We do an conservative estimate: when call is executed N times more often
2152 than the statement defining value, we take the frequency 1/N. */
2153 if (TREE_CODE (op
) == SSA_NAME
)
2158 return REG_BR_PROB_BASE
;
2160 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2161 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2163 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2167 if (init_freq
< bb
->frequency
)
2168 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2170 return REG_BR_PROB_BASE
;
2173 base
= get_base_address (op
);
2178 struct record_modified_bb_info info
;
2181 tree init
= ctor_for_folding (base
);
2183 if (init
!= error_mark_node
)
2186 return REG_BR_PROB_BASE
;
2187 ao_ref_init (&refd
, op
);
2189 info
.bb_set
= BITMAP_ALLOC (NULL
);
2190 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2192 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2194 BITMAP_FREE (info
.bb_set
);
2195 return REG_BR_PROB_BASE
;
2198 /* Assume that every memory is initialized at entry.
2199 TODO: Can we easilly determine if value is always defined
2200 and thus we may skip entry block? */
2201 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2202 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2206 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2207 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2209 BITMAP_FREE (info
.bb_set
);
2210 if (max
< bb
->frequency
)
2211 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2213 return REG_BR_PROB_BASE
;
2215 return REG_BR_PROB_BASE
;
2218 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2219 sub-graph and if the predicate the condition depends on is known. If so,
2220 return true and store the pointer the predicate in *P. */
2223 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2224 struct inline_summary
*summary
, basic_block bb
,
2225 struct predicate
*p
,
2226 vec
<predicate_t
> nonconstant_names
)
2230 basic_block first_bb
= NULL
;
2233 if (single_pred_p (bb
))
2235 *p
= false_predicate ();
2239 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2241 if (single_succ_p (e
->src
))
2243 if (!single_pred_p (e
->src
))
2246 first_bb
= single_pred (e
->src
);
2247 else if (single_pred (e
->src
) != first_bb
)
2254 else if (e
->src
!= first_bb
)
2262 stmt
= last_stmt (first_bb
);
2264 || gimple_code (stmt
) != GIMPLE_COND
2265 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2268 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2269 gimple_cond_lhs (stmt
),
2271 if (true_predicate_p (p
))
2277 /* Given a PHI statement in a function described by inline properties SUMMARY
2278 and *P being the predicate describing whether the selected PHI argument is
2279 known, store a predicate for the result of the PHI statement into
2280 NONCONSTANT_NAMES, if possible. */
2283 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2284 struct predicate
*p
,
2285 vec
<predicate_t
> nonconstant_names
)
2289 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2291 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2292 if (!is_gimple_min_invariant (arg
))
2294 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2295 *p
= or_predicates (summary
->conds
, p
,
2296 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2297 if (true_predicate_p (p
))
2302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2304 fprintf (dump_file
, "\t\tphi predicate: ");
2305 dump_predicate (dump_file
, summary
->conds
, p
);
2307 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2310 /* Return predicate specifying when array index in access OP becomes non-constant. */
2312 static struct predicate
2313 array_index_predicate (struct inline_summary
*info
,
2314 vec
< predicate_t
> nonconstant_names
, tree op
)
2316 struct predicate p
= false_predicate ();
2317 while (handled_component_p (op
))
2319 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2321 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2322 p
= or_predicates (info
->conds
, &p
,
2323 &nonconstant_names
[SSA_NAME_VERSION
2324 (TREE_OPERAND (op
, 1))]);
2326 op
= TREE_OPERAND (op
, 0);
2331 /* For a typical usage of __builtin_expect (a<b, 1), we
2332 may introduce an extra relation stmt:
2333 With the builtin, we have
2336 t3 = __builtin_expect (t2, 1);
2339 Without the builtin, we have
2342 This affects the size/time estimation and may have
2343 an impact on the earlier inlining.
2344 Here find this pattern and fix it up later. */
2347 find_foldable_builtin_expect (basic_block bb
)
2349 gimple_stmt_iterator bsi
;
2351 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2353 gimple stmt
= gsi_stmt (bsi
);
2354 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2355 || (is_gimple_call (stmt
)
2356 && gimple_call_internal_p (stmt
)
2357 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2359 tree var
= gimple_call_lhs (stmt
);
2360 tree arg
= gimple_call_arg (stmt
, 0);
2361 use_operand_p use_p
;
2368 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2370 while (TREE_CODE (arg
) == SSA_NAME
)
2372 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2373 if (!is_gimple_assign (stmt_tmp
))
2375 switch (gimple_assign_rhs_code (stmt_tmp
))
2394 arg
= gimple_assign_rhs1 (stmt_tmp
);
2397 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2398 && gimple_code (use_stmt
) == GIMPLE_COND
)
2405 /* Return true when the basic blocks contains only clobbers followed by RESX.
2406 Such BBs are kept around to make removal of dead stores possible with
2407 presence of EH and will be optimized out by optimize_clobbers later in the
2410 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2411 that can be clobber only, too.. When it is false, the RESX is not necessary
2412 on the end of basic block. */
2415 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2417 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2423 if (gsi_end_p (gsi
))
2425 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2429 else if (!single_succ_p (bb
))
2432 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2434 gimple stmt
= gsi_stmt (gsi
);
2435 if (is_gimple_debug (stmt
))
2437 if (gimple_clobber_p (stmt
))
2439 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2444 /* See if all predecestors are either throws or clobber only BBs. */
2445 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2446 if (!(e
->flags
& EDGE_EH
)
2447 && !clobber_only_eh_bb_p (e
->src
, false))
2453 /* Compute function body size parameters for NODE.
2454 When EARLY is true, we compute only simple summaries without
2455 non-trivial predicates to drive the early inliner. */
2458 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2461 /* Estimate static overhead for function prologue/epilogue and alignment. */
2463 /* Benefits are scaled by probability of elimination that is in range
2466 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2468 struct inline_summary
*info
= inline_summary (node
);
2469 struct predicate bb_predicate
;
2470 struct ipa_node_params
*parms_info
= NULL
;
2471 vec
<predicate_t
> nonconstant_names
= vNULL
;
2474 predicate array_index
= true_predicate ();
2475 gimple fix_builtin_expect_stmt
;
2480 if (opt_for_fn (node
->decl
, optimize
) && !early
)
2482 calculate_dominance_info (CDI_DOMINATORS
);
2483 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2485 if (ipa_node_params_vector
.exists ())
2487 parms_info
= IPA_NODE_REF (node
);
2488 nonconstant_names
.safe_grow_cleared
2489 (SSANAMES (my_function
)->length ());
2494 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2497 /* When we run into maximal number of entries, we assign everything to the
2498 constant truth case. Be sure to have it in list. */
2499 bb_predicate
= true_predicate ();
2500 account_size_time (info
, 0, 0, &bb_predicate
);
2502 bb_predicate
= not_inlined_predicate ();
2503 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2505 gcc_assert (my_function
&& my_function
->cfg
);
2507 compute_bb_predicates (node
, parms_info
, info
);
2508 gcc_assert (cfun
== my_function
);
2509 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2510 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2511 for (n
= 0; n
< nblocks
; n
++)
2513 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2514 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2515 if (clobber_only_eh_bb_p (bb
))
2517 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2518 fprintf (dump_file
, "\n Ignoring BB %i;"
2519 " it will be optimized away by cleanup_clobbers\n",
2524 /* TODO: Obviously predicates can be propagated down across CFG. */
2528 bb_predicate
= *(struct predicate
*) bb
->aux
;
2530 bb_predicate
= false_predicate ();
2533 bb_predicate
= true_predicate ();
2535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2537 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2538 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2541 if (parms_info
&& nonconstant_names
.exists ())
2543 struct predicate phi_predicate
;
2544 bool first_phi
= true;
2546 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2550 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2555 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2557 fprintf (dump_file
, " ");
2558 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2560 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2565 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2567 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2570 gimple stmt
= gsi_stmt (bsi
);
2571 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2572 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2574 struct predicate will_be_nonconstant
;
2576 /* This relation stmt should be folded after we remove
2577 buildin_expect call. Adjust the cost here. */
2578 if (stmt
== fix_builtin_expect_stmt
)
2584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2586 fprintf (dump_file
, " ");
2587 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2588 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2589 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2593 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2595 struct predicate this_array_index
;
2597 array_index_predicate (info
, nonconstant_names
,
2598 gimple_assign_rhs1 (stmt
));
2599 if (!false_predicate_p (&this_array_index
))
2601 and_predicates (info
->conds
, &array_index
,
2604 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2606 struct predicate this_array_index
;
2608 array_index_predicate (info
, nonconstant_names
,
2609 gimple_get_lhs (stmt
));
2610 if (!false_predicate_p (&this_array_index
))
2612 and_predicates (info
->conds
, &array_index
,
2617 if (is_gimple_call (stmt
)
2618 && !gimple_call_internal_p (stmt
))
2620 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2621 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2623 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2624 resolved as constant. We however don't want to optimize
2625 out the cgraph edges. */
2626 if (nonconstant_names
.exists ()
2627 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2628 && gimple_call_lhs (stmt
)
2629 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2631 struct predicate false_p
= false_predicate ();
2632 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2635 if (ipa_node_params_vector
.exists ())
2637 int count
= gimple_call_num_args (stmt
);
2641 es
->param
.safe_grow_cleared (count
);
2642 for (i
= 0; i
< count
; i
++)
2644 int prob
= param_change_prob (stmt
, i
);
2645 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2646 es
->param
[i
].change_prob
= prob
;
2650 es
->call_stmt_size
= this_size
;
2651 es
->call_stmt_time
= this_time
;
2652 es
->loop_depth
= bb_loop_depth (bb
);
2653 edge_set_predicate (edge
, &bb_predicate
);
2656 /* TODO: When conditional jump or swithc is known to be constant, but
2657 we did not translate it into the predicates, we really can account
2658 just maximum of the possible paths. */
2661 = will_be_nonconstant_predicate (parms_info
, info
,
2662 stmt
, nonconstant_names
);
2663 if (this_time
|| this_size
)
2669 prob
= eliminated_by_inlining_prob (stmt
);
2670 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2672 "\t\t50%% will be eliminated by inlining\n");
2673 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2674 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2677 p
= and_predicates (info
->conds
, &bb_predicate
,
2678 &will_be_nonconstant
);
2680 p
= true_predicate ();
2682 if (!false_predicate_p (&p
))
2686 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2687 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2690 /* We account everything but the calls. Calls have their own
2691 size/time info attached to cgraph edges. This is necessary
2692 in order to make the cost disappear after inlining. */
2693 if (!is_gimple_call (stmt
))
2697 struct predicate ip
= not_inlined_predicate ();
2698 ip
= and_predicates (info
->conds
, &ip
, &p
);
2699 account_size_time (info
, this_size
* prob
,
2700 this_time
* prob
, &ip
);
2703 account_size_time (info
, this_size
* (2 - prob
),
2704 this_time
* (2 - prob
), &p
);
2707 gcc_assert (time
>= 0);
2708 gcc_assert (size
>= 0);
2712 set_hint_predicate (&inline_summary (node
)->array_index
, array_index
);
2713 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2714 if (time
> MAX_TIME
)
2718 if (!early
&& nonconstant_names
.exists ())
2721 predicate loop_iterations
= true_predicate ();
2722 predicate loop_stride
= true_predicate ();
2724 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2725 flow_loops_dump (dump_file
, NULL
, 0);
2727 FOR_EACH_LOOP (loop
, 0)
2732 struct tree_niter_desc niter_desc
;
2733 basic_block
*body
= get_loop_body (loop
);
2734 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2736 exits
= get_loop_exit_edges (loop
);
2737 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2738 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2739 && !is_gimple_min_invariant (niter_desc
.niter
))
2741 predicate will_be_nonconstant
2742 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2745 if (!true_predicate_p (&will_be_nonconstant
))
2746 will_be_nonconstant
= and_predicates (info
->conds
,
2748 &will_be_nonconstant
);
2749 if (!true_predicate_p (&will_be_nonconstant
)
2750 && !false_predicate_p (&will_be_nonconstant
))
2751 /* This is slightly inprecise. We may want to represent each
2752 loop with independent predicate. */
2754 and_predicates (info
->conds
, &loop_iterations
,
2755 &will_be_nonconstant
);
2759 for (i
= 0; i
< loop
->num_nodes
; i
++)
2761 gimple_stmt_iterator gsi
;
2762 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2763 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2766 gimple stmt
= gsi_stmt (gsi
);
2771 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2773 predicate will_be_nonconstant
;
2776 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2777 || is_gimple_min_invariant (iv
.step
))
2780 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2783 if (!true_predicate_p (&will_be_nonconstant
))
2785 = and_predicates (info
->conds
,
2787 &will_be_nonconstant
);
2788 if (!true_predicate_p (&will_be_nonconstant
)
2789 && !false_predicate_p (&will_be_nonconstant
))
2790 /* This is slightly inprecise. We may want to represent
2791 each loop with independent predicate. */
2793 and_predicates (info
->conds
, &loop_stride
,
2794 &will_be_nonconstant
);
2800 set_hint_predicate (&inline_summary (node
)->loop_iterations
,
2802 set_hint_predicate (&inline_summary (node
)->loop_stride
, loop_stride
);
2805 FOR_ALL_BB_FN (bb
, my_function
)
2811 pool_free (edge_predicate_pool
, bb
->aux
);
2813 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2816 pool_free (edge_predicate_pool
, e
->aux
);
2820 inline_summary (node
)->self_time
= time
;
2821 inline_summary (node
)->self_size
= size
;
2822 nonconstant_names
.release ();
2823 if (opt_for_fn (node
->decl
, optimize
) && !early
)
2825 loop_optimizer_finalize ();
2826 free_dominance_info (CDI_DOMINATORS
);
2830 fprintf (dump_file
, "\n");
2831 dump_inline_summary (dump_file
, node
);
2836 /* Compute parameters of functions used by inliner.
2837 EARLY is true when we compute parameters for the early inliner */
2840 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2842 HOST_WIDE_INT self_stack_size
;
2843 struct cgraph_edge
*e
;
2844 struct inline_summary
*info
;
2846 gcc_assert (!node
->global
.inlined_to
);
2848 inline_summary_alloc ();
2850 info
= inline_summary (node
);
2851 reset_inline_summary (node
);
2853 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2854 Once this happen, we will need to more curefully predict call
2856 if (node
->thunk
.thunk_p
)
2858 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2859 struct predicate t
= true_predicate ();
2861 info
->inlinable
= 0;
2862 node
->callees
->call_stmt_cannot_inline_p
= true;
2863 node
->local
.can_change_signature
= false;
2864 es
->call_stmt_time
= 1;
2865 es
->call_stmt_size
= 1;
2866 account_size_time (info
, 0, 0, &t
);
2870 /* Even is_gimple_min_invariant rely on current_function_decl. */
2871 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2873 /* Estimate the stack size for the function if we're optimizing. */
2874 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2875 info
->estimated_self_stack_size
= self_stack_size
;
2876 info
->estimated_stack_size
= self_stack_size
;
2877 info
->stack_frame_offset
= 0;
2879 /* Can this function be inlined at all? */
2880 if (!opt_for_fn (node
->decl
, optimize
)
2881 && !lookup_attribute ("always_inline",
2882 DECL_ATTRIBUTES (node
->decl
)))
2883 info
->inlinable
= false;
2885 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2887 /* Type attributes can use parameter indices to describe them. */
2888 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2889 node
->local
.can_change_signature
= false;
2892 /* Otherwise, inlinable functions always can change signature. */
2893 if (info
->inlinable
)
2894 node
->local
.can_change_signature
= true;
2897 /* Functions calling builtin_apply can not change signature. */
2898 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2900 tree
cdecl = e
->callee
->decl
;
2901 if (DECL_BUILT_IN (cdecl)
2902 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2903 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2904 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2907 node
->local
.can_change_signature
= !e
;
2910 estimate_function_body_sizes (node
, early
);
2912 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2913 if (e
->callee
->comdat_local_p ())
2915 node
->calls_comdat_local
= (e
!= NULL
);
2917 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2918 info
->time
= info
->self_time
;
2919 info
->size
= info
->self_size
;
2920 info
->stack_frame_offset
= 0;
2921 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2922 #ifdef ENABLE_CHECKING
2923 inline_update_overall_summary (node
);
2924 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2931 /* Compute parameters of functions used by inliner using
2932 current_function_decl. */
2935 compute_inline_parameters_for_current (void)
2937 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2943 const pass_data pass_data_inline_parameters
=
2945 GIMPLE_PASS
, /* type */
2946 "inline_param", /* name */
2947 OPTGROUP_INLINE
, /* optinfo_flags */
2948 TV_INLINE_PARAMETERS
, /* tv_id */
2949 0, /* properties_required */
2950 0, /* properties_provided */
2951 0, /* properties_destroyed */
2952 0, /* todo_flags_start */
2953 0, /* todo_flags_finish */
2956 class pass_inline_parameters
: public gimple_opt_pass
2959 pass_inline_parameters (gcc::context
*ctxt
)
2960 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
2963 /* opt_pass methods: */
2964 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
2965 virtual unsigned int execute (function
*)
2967 return compute_inline_parameters_for_current ();
2970 }; // class pass_inline_parameters
2975 make_pass_inline_parameters (gcc::context
*ctxt
)
2977 return new pass_inline_parameters (ctxt
);
2981 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
2982 KNOWN_CONTEXTS and KNOWN_AGGS. */
2985 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
2986 int *size
, int *time
,
2987 vec
<tree
> known_vals
,
2988 vec
<ipa_polymorphic_call_context
> known_contexts
,
2989 vec
<ipa_agg_jump_function_p
> known_aggs
)
2992 struct cgraph_node
*callee
;
2993 struct inline_summary
*isummary
;
2994 enum availability avail
;
2997 if (!known_vals
.exists () && !known_contexts
.exists ())
2999 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3002 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3003 known_aggs
, &speculative
);
3004 if (!target
|| speculative
)
3007 /* Account for difference in cost between indirect and direct calls. */
3008 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3009 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3010 gcc_checking_assert (*time
>= 0);
3011 gcc_checking_assert (*size
>= 0);
3013 callee
= cgraph_node::get (target
);
3014 if (!callee
|| !callee
->definition
)
3016 callee
= callee
->function_symbol (&avail
);
3017 if (avail
< AVAIL_AVAILABLE
)
3019 isummary
= inline_summary (callee
);
3020 return isummary
->inlinable
;
3023 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3024 handle edge E with probability PROB.
3025 Set HINTS if edge may be devirtualized.
3026 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3030 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3033 vec
<tree
> known_vals
,
3034 vec
<ipa_polymorphic_call_context
> known_contexts
,
3035 vec
<ipa_agg_jump_function_p
> known_aggs
,
3036 inline_hints
*hints
)
3038 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3039 int call_size
= es
->call_stmt_size
;
3040 int call_time
= es
->call_stmt_time
;
3043 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3044 known_vals
, known_contexts
, known_aggs
)
3045 && hints
&& e
->maybe_hot_p ())
3046 *hints
|= INLINE_HINT_indirect_call
;
3047 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3050 *min_size
+= cur_size
;
3051 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3052 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3053 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3054 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3059 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3060 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3061 describe context of the call site. */
3064 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3065 int *min_size
, int *time
,
3066 inline_hints
*hints
,
3067 clause_t possible_truths
,
3068 vec
<tree
> known_vals
,
3069 vec
<ipa_polymorphic_call_context
> known_contexts
,
3070 vec
<ipa_agg_jump_function_p
> known_aggs
)
3072 struct cgraph_edge
*e
;
3073 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3075 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3077 || evaluate_predicate (es
->predicate
, possible_truths
))
3079 if (e
->inline_failed
)
3081 /* Predicates of calls shall not use NOT_CHANGED codes,
3082 sowe do not need to compute probabilities. */
3083 estimate_edge_size_and_time (e
, size
,
3084 es
->predicate
? NULL
: min_size
,
3085 time
, REG_BR_PROB_BASE
,
3086 known_vals
, known_contexts
,
3090 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3093 known_vals
, known_contexts
,
3097 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3099 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3101 || evaluate_predicate (es
->predicate
, possible_truths
))
3102 estimate_edge_size_and_time (e
, size
,
3103 es
->predicate
? NULL
: min_size
,
3104 time
, REG_BR_PROB_BASE
,
3105 known_vals
, known_contexts
, known_aggs
,
3111 /* Estimate size and time needed to execute NODE assuming
3112 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3113 information about NODE's arguments. If non-NULL use also probability
3114 information present in INLINE_PARAM_SUMMARY vector.
3115 Additionally detemine hints determined by the context. Finally compute
3116 minimal size needed for the call that is independent on the call context and
3117 can be used for fast estimates. Return the values in RET_SIZE,
3118 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3121 estimate_node_size_and_time (struct cgraph_node
*node
,
3122 clause_t possible_truths
,
3123 vec
<tree
> known_vals
,
3124 vec
<ipa_polymorphic_call_context
> known_contexts
,
3125 vec
<ipa_agg_jump_function_p
> known_aggs
,
3126 int *ret_size
, int *ret_min_size
, int *ret_time
,
3127 inline_hints
*ret_hints
,
3128 vec
<inline_param_summary
>
3129 inline_param_summary
)
3131 struct inline_summary
*info
= inline_summary (node
);
3136 inline_hints hints
= 0;
3139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3142 fprintf (dump_file
, " Estimating body: %s/%i\n"
3143 " Known to be false: ", node
->name (),
3146 for (i
= predicate_not_inlined_condition
;
3147 i
< (predicate_first_dynamic_condition
3148 + (int) vec_safe_length (info
->conds
)); i
++)
3149 if (!(possible_truths
& (1 << i
)))
3152 fprintf (dump_file
, ", ");
3154 dump_condition (dump_file
, info
->conds
, i
);
3158 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3159 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3162 gcc_checking_assert (e
->time
>= 0);
3163 gcc_checking_assert (time
>= 0);
3164 if (!inline_param_summary
.exists ())
3168 int prob
= predicate_probability (info
->conds
,
3171 inline_param_summary
);
3172 gcc_checking_assert (prob
>= 0);
3173 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3174 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3176 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3177 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3178 gcc_checking_assert (time
>= 0);
3181 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3182 min_size
= (*info
->entry
)[0].size
;
3183 gcc_checking_assert (size
>= 0);
3184 gcc_checking_assert (time
>= 0);
3186 if (info
->loop_iterations
3187 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3188 hints
|= INLINE_HINT_loop_iterations
;
3189 if (info
->loop_stride
3190 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3191 hints
|= INLINE_HINT_loop_stride
;
3192 if (info
->array_index
3193 && !evaluate_predicate (info
->array_index
, possible_truths
))
3194 hints
|= INLINE_HINT_array_index
;
3196 hints
|= INLINE_HINT_in_scc
;
3197 if (DECL_DECLARED_INLINE_P (node
->decl
))
3198 hints
|= INLINE_HINT_declared_inline
;
3200 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3201 known_vals
, known_contexts
, known_aggs
);
3202 gcc_checking_assert (size
>= 0);
3203 gcc_checking_assert (time
>= 0);
3204 time
= RDIV (time
, INLINE_TIME_SCALE
);
3205 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3206 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3208 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3209 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3215 *ret_min_size
= min_size
;
3222 /* Estimate size and time needed to execute callee of EDGE assuming that
3223 parameters known to be constant at caller of EDGE are propagated.
3224 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3225 and types for parameters. */
3228 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3229 vec
<tree
> known_vals
,
3230 vec
<ipa_polymorphic_call_context
>
3232 vec
<ipa_agg_jump_function_p
> known_aggs
,
3233 int *ret_size
, int *ret_time
,
3234 inline_hints
*hints
)
3238 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3240 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3241 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3244 /* Translate all conditions from callee representation into caller
3245 representation and symbolically evaluate predicate P into new predicate.
3247 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3248 is summary of function predicate P is from. OPERAND_MAP is array giving
3249 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3250 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3251 predicate under which callee is executed. OFFSET_MAP is an array of of
3252 offsets that need to be added to conditions, negative offset means that
3253 conditions relying on values passed by reference have to be discarded
3254 because they might not be preserved (and should be considered offset zero
3255 for other purposes). */
3257 static struct predicate
3258 remap_predicate (struct inline_summary
*info
,
3259 struct inline_summary
*callee_info
,
3260 struct predicate
*p
,
3261 vec
<int> operand_map
,
3262 vec
<int> offset_map
,
3263 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3266 struct predicate out
= true_predicate ();
3268 /* True predicate is easy. */
3269 if (true_predicate_p (p
))
3270 return *toplev_predicate
;
3271 for (i
= 0; p
->clause
[i
]; i
++)
3273 clause_t clause
= p
->clause
[i
];
3275 struct predicate clause_predicate
= false_predicate ();
3277 gcc_assert (i
< MAX_CLAUSES
);
3279 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3280 /* Do we have condition we can't disprove? */
3281 if (clause
& possible_truths
& (1 << cond
))
3283 struct predicate cond_predicate
;
3284 /* Work out if the condition can translate to predicate in the
3285 inlined function. */
3286 if (cond
>= predicate_first_dynamic_condition
)
3288 struct condition
*c
;
3290 c
= &(*callee_info
->conds
)[cond
3292 predicate_first_dynamic_condition
];
3293 /* See if we can remap condition operand to caller's operand.
3294 Otherwise give up. */
3295 if (!operand_map
.exists ()
3296 || (int) operand_map
.length () <= c
->operand_num
3297 || operand_map
[c
->operand_num
] == -1
3298 /* TODO: For non-aggregate conditions, adding an offset is
3299 basically an arithmetic jump function processing which
3300 we should support in future. */
3301 || ((!c
->agg_contents
|| !c
->by_ref
)
3302 && offset_map
[c
->operand_num
] > 0)
3303 || (c
->agg_contents
&& c
->by_ref
3304 && offset_map
[c
->operand_num
] < 0))
3305 cond_predicate
= true_predicate ();
3308 struct agg_position_info ap
;
3309 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3310 if (offset_delta
< 0)
3312 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3315 gcc_assert (!c
->agg_contents
3316 || c
->by_ref
|| offset_delta
== 0);
3317 ap
.offset
= c
->offset
+ offset_delta
;
3318 ap
.agg_contents
= c
->agg_contents
;
3319 ap
.by_ref
= c
->by_ref
;
3320 cond_predicate
= add_condition (info
,
3321 operand_map
[c
->operand_num
],
3322 &ap
, c
->code
, c
->val
);
3325 /* Fixed conditions remains same, construct single
3326 condition predicate. */
3329 cond_predicate
.clause
[0] = 1 << cond
;
3330 cond_predicate
.clause
[1] = 0;
3332 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3335 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3337 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3341 /* Update summary information of inline clones after inlining.
3342 Compute peak stack usage. */
3345 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3347 struct cgraph_edge
*e
;
3348 struct inline_summary
*callee_info
= inline_summary (node
);
3349 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
3352 callee_info
->stack_frame_offset
3353 = caller_info
->stack_frame_offset
3354 + caller_info
->estimated_self_stack_size
;
3355 peak
= callee_info
->stack_frame_offset
3356 + callee_info
->estimated_self_stack_size
;
3357 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3358 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3359 ipa_propagate_frequency (node
);
3360 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3362 if (!e
->inline_failed
)
3363 inline_update_callee_summaries (e
->callee
, depth
);
3364 inline_edge_summary (e
)->loop_depth
+= depth
;
3366 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3367 inline_edge_summary (e
)->loop_depth
+= depth
;
3370 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3371 When functoin A is inlined in B and A calls C with parameter that
3372 changes with probability PROB1 and C is known to be passthroug
3373 of argument if B that change with probability PROB2, the probability
3374 of change is now PROB1*PROB2. */
3377 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3378 struct cgraph_edge
*edge
)
3380 if (ipa_node_params_vector
.exists ())
3383 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3384 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3385 struct inline_edge_summary
*inlined_es
3386 = inline_edge_summary (inlined_edge
);
3388 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3390 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3391 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3392 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3393 < (int) inlined_es
->param
.length ()))
3395 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3396 int prob1
= es
->param
[i
].change_prob
;
3397 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3398 int prob
= combine_probabilities (prob1
, prob2
);
3400 if (prob1
&& prob2
&& !prob
)
3403 es
->param
[i
].change_prob
= prob
;
3409 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3411 Remap predicates of callees of NODE. Rest of arguments match
3414 Also update change probabilities. */
3417 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3418 struct cgraph_node
*node
,
3419 struct inline_summary
*info
,
3420 struct inline_summary
*callee_info
,
3421 vec
<int> operand_map
,
3422 vec
<int> offset_map
,
3423 clause_t possible_truths
,
3424 struct predicate
*toplev_predicate
)
3426 struct cgraph_edge
*e
;
3427 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3429 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3432 if (e
->inline_failed
)
3434 remap_edge_change_prob (inlined_edge
, e
);
3438 p
= remap_predicate (info
, callee_info
,
3439 es
->predicate
, operand_map
, offset_map
,
3440 possible_truths
, toplev_predicate
);
3441 edge_set_predicate (e
, &p
);
3442 /* TODO: We should remove the edge for code that will be
3443 optimized out, but we need to keep verifiers and tree-inline
3444 happy. Make it cold for now. */
3445 if (false_predicate_p (&p
))
3452 edge_set_predicate (e
, toplev_predicate
);
3455 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3456 operand_map
, offset_map
, possible_truths
,
3459 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3461 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3464 remap_edge_change_prob (inlined_edge
, e
);
3467 p
= remap_predicate (info
, callee_info
,
3468 es
->predicate
, operand_map
, offset_map
,
3469 possible_truths
, toplev_predicate
);
3470 edge_set_predicate (e
, &p
);
3471 /* TODO: We should remove the edge for code that will be optimized
3472 out, but we need to keep verifiers and tree-inline happy.
3473 Make it cold for now. */
3474 if (false_predicate_p (&p
))
3481 edge_set_predicate (e
, toplev_predicate
);
3485 /* Same as remap_predicate, but set result into hint *HINT. */
3488 remap_hint_predicate (struct inline_summary
*info
,
3489 struct inline_summary
*callee_info
,
3490 struct predicate
**hint
,
3491 vec
<int> operand_map
,
3492 vec
<int> offset_map
,
3493 clause_t possible_truths
,
3494 struct predicate
*toplev_predicate
)
3500 p
= remap_predicate (info
, callee_info
,
3502 operand_map
, offset_map
,
3503 possible_truths
, toplev_predicate
);
3504 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3507 set_hint_predicate (hint
, p
);
3509 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3513 /* We inlined EDGE. Update summary of the function we inlined into. */
3516 inline_merge_summary (struct cgraph_edge
*edge
)
3518 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
3519 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3520 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3521 struct inline_summary
*info
= inline_summary (to
);
3522 clause_t clause
= 0; /* not_inline is known to be false. */
3524 vec
<int> operand_map
= vNULL
;
3525 vec
<int> offset_map
= vNULL
;
3527 struct predicate toplev_predicate
;
3528 struct predicate true_p
= true_predicate ();
3529 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3532 toplev_predicate
= *es
->predicate
;
3534 toplev_predicate
= true_predicate ();
3536 if (ipa_node_params_vector
.exists () && callee_info
->conds
)
3538 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3539 int count
= ipa_get_cs_argument_count (args
);
3542 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3545 operand_map
.safe_grow_cleared (count
);
3546 offset_map
.safe_grow_cleared (count
);
3548 for (i
= 0; i
< count
; i
++)
3550 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3553 /* TODO: handle non-NOPs when merging. */
3554 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3556 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3557 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3558 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3561 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3563 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3564 if (offset
>= 0 && offset
< INT_MAX
)
3566 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3567 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3569 offset_map
[i
] = offset
;
3572 operand_map
[i
] = map
;
3573 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3576 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3578 struct predicate p
= remap_predicate (info
, callee_info
,
3579 &e
->predicate
, operand_map
,
3582 if (!false_predicate_p (&p
))
3584 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3585 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3586 int prob
= predicate_probability (callee_info
->conds
,
3589 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3590 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3591 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3592 if (prob
!= REG_BR_PROB_BASE
3593 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3595 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3596 (double) prob
/ REG_BR_PROB_BASE
);
3598 account_size_time (info
, e
->size
, add_time
, &p
);
3601 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3602 offset_map
, clause
, &toplev_predicate
);
3603 remap_hint_predicate (info
, callee_info
,
3604 &callee_info
->loop_iterations
,
3605 operand_map
, offset_map
, clause
, &toplev_predicate
);
3606 remap_hint_predicate (info
, callee_info
,
3607 &callee_info
->loop_stride
,
3608 operand_map
, offset_map
, clause
, &toplev_predicate
);
3609 remap_hint_predicate (info
, callee_info
,
3610 &callee_info
->array_index
,
3611 operand_map
, offset_map
, clause
, &toplev_predicate
);
3613 inline_update_callee_summaries (edge
->callee
,
3614 inline_edge_summary (edge
)->loop_depth
);
3616 /* We do not maintain predicates of inlined edges, free it. */
3617 edge_set_predicate (edge
, &true_p
);
3618 /* Similarly remove param summaries. */
3619 es
->param
.release ();
3620 operand_map
.release ();
3621 offset_map
.release ();
3624 /* For performance reasons inline_merge_summary is not updating overall size
3625 and time. Recompute it. */
3628 inline_update_overall_summary (struct cgraph_node
*node
)
3630 struct inline_summary
*info
= inline_summary (node
);
3636 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3638 info
->size
+= e
->size
, info
->time
+= e
->time
;
3639 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3640 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3642 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3644 ~(clause_t
) (1 << predicate_false_condition
),
3645 vNULL
, vNULL
, vNULL
);
3646 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3647 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3650 /* Return hints derrived from EDGE. */
3652 simple_edge_hints (struct cgraph_edge
*edge
)
3655 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3656 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3657 if (inline_summary (to
)->scc_no
3658 && inline_summary (to
)->scc_no
== inline_summary (edge
->callee
)->scc_no
3659 && !edge
->recursive_p ())
3660 hints
|= INLINE_HINT_same_scc
;
3662 if (to
->lto_file_data
&& edge
->callee
->lto_file_data
3663 && to
->lto_file_data
!= edge
->callee
->lto_file_data
)
3664 hints
|= INLINE_HINT_cross_module
;
3669 /* Estimate the time cost for the caller when inlining EDGE.
3670 Only to be called via estimate_edge_time, that handles the
3673 When caching, also update the cache entry. Compute both time and
3674 size, since we always need both metrics eventually. */
3677 do_estimate_edge_time (struct cgraph_edge
*edge
)
3682 struct cgraph_node
*callee
;
3684 vec
<tree
> known_vals
;
3685 vec
<ipa_polymorphic_call_context
> known_contexts
;
3686 vec
<ipa_agg_jump_function_p
> known_aggs
;
3687 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3690 callee
= edge
->callee
->ultimate_alias_target ();
3692 gcc_checking_assert (edge
->inline_failed
);
3693 evaluate_properties_for_edge (edge
, true,
3694 &clause
, &known_vals
, &known_contexts
,
3696 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3697 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3699 /* When we have profile feedback, we can quite safely identify hot
3700 edges and for those we disable size limits. Don't do that when
3701 probability that caller will call the callee is low however, since it
3702 may hurt optimization of the caller's hot path. */
3703 if (edge
->count
&& edge
->maybe_hot_p ()
3705 > (edge
->caller
->global
.inlined_to
3706 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3707 hints
|= INLINE_HINT_known_hot
;
3709 known_vals
.release ();
3710 known_contexts
.release ();
3711 known_aggs
.release ();
3712 gcc_checking_assert (size
>= 0);
3713 gcc_checking_assert (time
>= 0);
3715 /* When caching, update the cache entry. */
3716 if (edge_growth_cache
.exists ())
3718 inline_summary (edge
->callee
)->min_size
= min_size
;
3719 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3720 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3721 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3723 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3724 hints
|= simple_edge_hints (edge
);
3725 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3731 /* Return estimated callee growth after inlining EDGE.
3732 Only to be called via estimate_edge_size. */
3735 do_estimate_edge_size (struct cgraph_edge
*edge
)
3738 struct cgraph_node
*callee
;
3740 vec
<tree
> known_vals
;
3741 vec
<ipa_polymorphic_call_context
> known_contexts
;
3742 vec
<ipa_agg_jump_function_p
> known_aggs
;
3744 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3746 if (edge_growth_cache
.exists ())
3748 do_estimate_edge_time (edge
);
3749 size
= edge_growth_cache
[edge
->uid
].size
;
3750 gcc_checking_assert (size
);
3751 return size
- (size
> 0);
3754 callee
= edge
->callee
->ultimate_alias_target ();
3756 /* Early inliner runs without caching, go ahead and do the dirty work. */
3757 gcc_checking_assert (edge
->inline_failed
);
3758 evaluate_properties_for_edge (edge
, true,
3759 &clause
, &known_vals
, &known_contexts
,
3761 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3762 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3763 known_vals
.release ();
3764 known_contexts
.release ();
3765 known_aggs
.release ();
3770 /* Estimate the growth of the caller when inlining EDGE.
3771 Only to be called via estimate_edge_size. */
3774 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3777 struct cgraph_node
*callee
;
3779 vec
<tree
> known_vals
;
3780 vec
<ipa_polymorphic_call_context
> known_contexts
;
3781 vec
<ipa_agg_jump_function_p
> known_aggs
;
3783 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3785 if (edge_growth_cache
.exists ())
3787 do_estimate_edge_time (edge
);
3788 hints
= edge_growth_cache
[edge
->uid
].hints
;
3789 gcc_checking_assert (hints
);
3793 callee
= edge
->callee
->ultimate_alias_target ();
3795 /* Early inliner runs without caching, go ahead and do the dirty work. */
3796 gcc_checking_assert (edge
->inline_failed
);
3797 evaluate_properties_for_edge (edge
, true,
3798 &clause
, &known_vals
, &known_contexts
,
3800 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3801 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3802 known_vals
.release ();
3803 known_contexts
.release ();
3804 known_aggs
.release ();
3805 hints
|= simple_edge_hints (edge
);
3810 /* Estimate self time of the function NODE after inlining EDGE. */
3813 estimate_time_after_inlining (struct cgraph_node
*node
,
3814 struct cgraph_edge
*edge
)
3816 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3817 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3820 inline_summary (node
)->time
+ estimate_edge_time (edge
);
3823 if (time
> MAX_TIME
)
3827 return inline_summary (node
)->time
;
3831 /* Estimate the size of NODE after inlining EDGE which should be an
3832 edge to either NODE or a call inlined into NODE. */
3835 estimate_size_after_inlining (struct cgraph_node
*node
,
3836 struct cgraph_edge
*edge
)
3838 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3839 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3841 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
3842 gcc_assert (size
>= 0);
3845 return inline_summary (node
)->size
;
3851 struct cgraph_node
*node
;
3852 bool self_recursive
;
3857 /* Worker for do_estimate_growth. Collect growth for all callers. */
3860 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3862 struct cgraph_edge
*e
;
3863 struct growth_data
*d
= (struct growth_data
*) data
;
3865 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3867 gcc_checking_assert (e
->inline_failed
);
3869 if (e
->caller
== d
->node
3870 || (e
->caller
->global
.inlined_to
3871 && e
->caller
->global
.inlined_to
== d
->node
))
3872 d
->self_recursive
= true;
3873 d
->growth
+= estimate_edge_growth (e
);
3879 /* Estimate the growth caused by inlining NODE into all callees. */
3882 do_estimate_growth (struct cgraph_node
*node
)
3884 struct growth_data d
= { node
, 0, false };
3885 struct inline_summary
*info
= inline_summary (node
);
3887 node
->call_for_symbol_thunks_and_aliases (do_estimate_growth_1
, &d
, true);
3889 /* For self recursive functions the growth estimation really should be
3890 infinity. We don't want to return very large values because the growth
3891 plays various roles in badness computation fractions. Be sure to not
3892 return zero or negative growths. */
3893 if (d
.self_recursive
)
3894 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3895 else if (DECL_EXTERNAL (node
->decl
))
3899 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3900 d
.growth
-= info
->size
;
3901 /* COMDAT functions are very often not shared across multiple units
3902 since they come from various template instantiations.
3903 Take this into account. */
3904 else if (DECL_COMDAT (node
->decl
)
3905 && node
->can_remove_if_no_direct_calls_p ())
3906 d
.growth
-= (info
->size
3907 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3911 if (node_growth_cache
.exists ())
3913 if ((int) node_growth_cache
.length () <= node
->uid
)
3914 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
3915 node_growth_cache
[node
->uid
] = d
.growth
+ (d
.growth
>= 0);
3921 /* Make cheap estimation if growth of NODE is likely positive knowing
3922 EDGE_GROWTH of one particular edge.
3923 We assume that most of other edges will have similar growth
3924 and skip computation if there are too many callers. */
3927 growth_likely_positive (struct cgraph_node
*node
, int edge_growth ATTRIBUTE_UNUSED
)
3931 struct cgraph_edge
*e
;
3932 gcc_checking_assert (edge_growth
> 0);
3934 /* Unlike for functions called once, we play unsafe with
3935 COMDATs. We can allow that since we know functions
3936 in consideration are small (and thus risk is small) and
3937 moreover grow estimates already accounts that COMDAT
3938 functions may or may not disappear when eliminated from
3939 current unit. With good probability making aggressive
3940 choice in all units is going to make overall program
3943 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
3945 cgraph_will_be_removed_from_program_if_no_direct_calls */
3946 if (DECL_EXTERNAL (node
->decl
)
3947 || !node
->can_remove_if_no_direct_calls_p ())
3950 /* If there is cached value, just go ahead. */
3951 if ((int)node_growth_cache
.length () > node
->uid
3952 && (ret
= node_growth_cache
[node
->uid
]))
3954 if (!node
->will_be_removed_from_program_if_no_direct_calls_p ()
3955 && (!DECL_COMDAT (node
->decl
)
3956 || !node
->can_remove_if_no_direct_calls_p ()))
3958 max_callers
= inline_summary (node
)->size
* 4 / edge_growth
+ 2;
3960 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3966 return estimate_growth (node
) > 0;
3970 /* This function performs intraprocedural analysis in NODE that is required to
3971 inline indirect calls. */
3974 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
3976 ipa_analyze_node (node
);
3977 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3979 ipa_print_node_params (dump_file
, node
);
3980 ipa_print_node_jump_functions (dump_file
, node
);
3985 /* Note function body size. */
3988 inline_analyze_function (struct cgraph_node
*node
)
3990 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3993 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
3994 node
->name (), node
->order
);
3995 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
3996 inline_indirect_intraprocedural_analysis (node
);
3997 compute_inline_parameters (node
, false);
4000 struct cgraph_edge
*e
;
4001 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4003 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4004 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4005 e
->call_stmt_cannot_inline_p
= true;
4007 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4009 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4010 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4011 e
->call_stmt_cannot_inline_p
= true;
4019 /* Called when new function is inserted to callgraph late. */
4022 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
4024 inline_analyze_function (node
);
4028 /* Note function body size. */
4031 inline_generate_summary (void)
4033 struct cgraph_node
*node
;
4035 /* When not optimizing, do not bother to analyze. Inlining is still done
4036 because edge redirection needs to happen there. */
4037 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4040 function_insertion_hook_holder
=
4041 symtab
->add_cgraph_insertion_hook (&add_new_function
, NULL
);
4043 ipa_register_cgraph_hooks ();
4044 inline_free_summary ();
4046 FOR_EACH_DEFINED_FUNCTION (node
)
4048 inline_analyze_function (node
);
4052 /* Read predicate from IB. */
4054 static struct predicate
4055 read_predicate (struct lto_input_block
*ib
)
4057 struct predicate out
;
4063 gcc_assert (k
<= MAX_CLAUSES
);
4064 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4068 /* Zero-initialize the remaining clauses in OUT. */
4069 while (k
<= MAX_CLAUSES
)
4070 out
.clause
[k
++] = 0;
4076 /* Write inline summary for edge E to OB. */
4079 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4081 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4085 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4086 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4087 es
->loop_depth
= streamer_read_uhwi (ib
);
4088 p
= read_predicate (ib
);
4089 edge_set_predicate (e
, &p
);
4090 length
= streamer_read_uhwi (ib
);
4093 es
->param
.safe_grow_cleared (length
);
4094 for (i
= 0; i
< length
; i
++)
4095 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4100 /* Stream in inline summaries from the section. */
4103 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4106 const struct lto_function_header
*header
=
4107 (const struct lto_function_header
*) data
;
4108 const int cfg_offset
= sizeof (struct lto_function_header
);
4109 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4110 const int string_offset
= main_offset
+ header
->main_size
;
4111 struct data_in
*data_in
;
4112 unsigned int i
, count2
, j
;
4113 unsigned int f_count
;
4115 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
);
4118 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4119 header
->string_size
, vNULL
);
4120 f_count
= streamer_read_uhwi (&ib
);
4121 for (i
= 0; i
< f_count
; i
++)
4124 struct cgraph_node
*node
;
4125 struct inline_summary
*info
;
4126 lto_symtab_encoder_t encoder
;
4127 struct bitpack_d bp
;
4128 struct cgraph_edge
*e
;
4131 index
= streamer_read_uhwi (&ib
);
4132 encoder
= file_data
->symtab_node_encoder
;
4133 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4135 info
= inline_summary (node
);
4137 info
->estimated_stack_size
4138 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4139 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4140 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4142 bp
= streamer_read_bitpack (&ib
);
4143 info
->inlinable
= bp_unpack_value (&bp
, 1);
4145 count2
= streamer_read_uhwi (&ib
);
4146 gcc_assert (!info
->conds
);
4147 for (j
= 0; j
< count2
; j
++)
4150 c
.operand_num
= streamer_read_uhwi (&ib
);
4151 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4152 c
.val
= stream_read_tree (&ib
, data_in
);
4153 bp
= streamer_read_bitpack (&ib
);
4154 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4155 c
.by_ref
= bp_unpack_value (&bp
, 1);
4157 c
.offset
= streamer_read_uhwi (&ib
);
4158 vec_safe_push (info
->conds
, c
);
4160 count2
= streamer_read_uhwi (&ib
);
4161 gcc_assert (!info
->entry
);
4162 for (j
= 0; j
< count2
; j
++)
4164 struct size_time_entry e
;
4166 e
.size
= streamer_read_uhwi (&ib
);
4167 e
.time
= streamer_read_uhwi (&ib
);
4168 e
.predicate
= read_predicate (&ib
);
4170 vec_safe_push (info
->entry
, e
);
4173 p
= read_predicate (&ib
);
4174 set_hint_predicate (&info
->loop_iterations
, p
);
4175 p
= read_predicate (&ib
);
4176 set_hint_predicate (&info
->loop_stride
, p
);
4177 p
= read_predicate (&ib
);
4178 set_hint_predicate (&info
->array_index
, p
);
4179 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4180 read_inline_edge_summary (&ib
, e
);
4181 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4182 read_inline_edge_summary (&ib
, e
);
4185 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4187 lto_data_in_delete (data_in
);
4191 /* Read inline summary. Jump functions are shared among ipa-cp
4192 and inliner, so when ipa-cp is active, we don't need to write them
4196 inline_read_summary (void)
4198 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4199 struct lto_file_decl_data
*file_data
;
4202 inline_summary_alloc ();
4204 while ((file_data
= file_data_vec
[j
++]))
4207 const char *data
= lto_get_section_data (file_data
,
4208 LTO_section_inline_summary
,
4211 inline_read_section (file_data
, data
, len
);
4213 /* Fatal error here. We do not want to support compiling ltrans units
4214 with different version of compiler or different flags than the WPA
4215 unit, so this should never happen. */
4216 fatal_error ("ipa inline summary is missing in input file");
4220 ipa_register_cgraph_hooks ();
4222 ipa_prop_read_jump_functions ();
4224 function_insertion_hook_holder
=
4225 symtab
->add_cgraph_insertion_hook (&add_new_function
, NULL
);
4229 /* Write predicate P to OB. */
4232 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4236 for (j
= 0; p
->clause
[j
]; j
++)
4238 gcc_assert (j
< MAX_CLAUSES
);
4239 streamer_write_uhwi (ob
, p
->clause
[j
]);
4241 streamer_write_uhwi (ob
, 0);
4245 /* Write inline summary for edge E to OB. */
4248 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4250 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4253 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4254 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4255 streamer_write_uhwi (ob
, es
->loop_depth
);
4256 write_predicate (ob
, es
->predicate
);
4257 streamer_write_uhwi (ob
, es
->param
.length ());
4258 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4259 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4263 /* Write inline summary for node in SET.
4264 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4265 active, we don't need to write them twice. */
4268 inline_write_summary (void)
4270 struct cgraph_node
*node
;
4271 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4272 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4273 unsigned int count
= 0;
4276 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4278 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4279 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4280 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4283 streamer_write_uhwi (ob
, count
);
4285 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4287 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4288 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4289 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4291 struct inline_summary
*info
= inline_summary (node
);
4292 struct bitpack_d bp
;
4293 struct cgraph_edge
*edge
;
4296 struct condition
*c
;
4298 streamer_write_uhwi (ob
,
4299 lto_symtab_encoder_encode (encoder
,
4302 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4303 streamer_write_hwi (ob
, info
->self_size
);
4304 streamer_write_hwi (ob
, info
->self_time
);
4305 bp
= bitpack_create (ob
->main_stream
);
4306 bp_pack_value (&bp
, info
->inlinable
, 1);
4307 streamer_write_bitpack (&bp
);
4308 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4309 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4311 streamer_write_uhwi (ob
, c
->operand_num
);
4312 streamer_write_uhwi (ob
, c
->code
);
4313 stream_write_tree (ob
, c
->val
, true);
4314 bp
= bitpack_create (ob
->main_stream
);
4315 bp_pack_value (&bp
, c
->agg_contents
, 1);
4316 bp_pack_value (&bp
, c
->by_ref
, 1);
4317 streamer_write_bitpack (&bp
);
4318 if (c
->agg_contents
)
4319 streamer_write_uhwi (ob
, c
->offset
);
4321 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4322 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4324 streamer_write_uhwi (ob
, e
->size
);
4325 streamer_write_uhwi (ob
, e
->time
);
4326 write_predicate (ob
, &e
->predicate
);
4328 write_predicate (ob
, info
->loop_iterations
);
4329 write_predicate (ob
, info
->loop_stride
);
4330 write_predicate (ob
, info
->array_index
);
4331 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4332 write_inline_edge_summary (ob
, edge
);
4333 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4334 write_inline_edge_summary (ob
, edge
);
4337 streamer_write_char_stream (ob
->main_stream
, 0);
4338 produce_asm (ob
, NULL
);
4339 destroy_output_block (ob
);
4341 if (optimize
&& !flag_ipa_cp
)
4342 ipa_prop_write_jump_functions ();
4346 /* Release inline summary. */
4349 inline_free_summary (void)
4351 struct cgraph_node
*node
;
4352 if (function_insertion_hook_holder
)
4353 symtab
->remove_cgraph_insertion_hook (function_insertion_hook_holder
);
4354 function_insertion_hook_holder
= NULL
;
4355 if (node_removal_hook_holder
)
4356 symtab
->remove_cgraph_removal_hook (node_removal_hook_holder
);
4357 node_removal_hook_holder
= NULL
;
4358 if (edge_removal_hook_holder
)
4359 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4360 edge_removal_hook_holder
= NULL
;
4361 if (node_duplication_hook_holder
)
4362 symtab
->remove_cgraph_duplication_hook (node_duplication_hook_holder
);
4363 node_duplication_hook_holder
= NULL
;
4364 if (edge_duplication_hook_holder
)
4365 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4366 edge_duplication_hook_holder
= NULL
;
4367 if (!inline_edge_summary_vec
.exists ())
4369 FOR_EACH_DEFINED_FUNCTION (node
)
4371 reset_inline_summary (node
);
4372 vec_free (inline_summary_vec
);
4373 inline_edge_summary_vec
.release ();
4374 if (edge_predicate_pool
)
4375 free_alloc_pool (edge_predicate_pool
);
4376 edge_predicate_pool
= 0;