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 (cc2
->code
,
383 HONOR_NANS (cc1
->val
)))
389 /* We run out of variants. Be conservative in positive direction. */
390 if (i2
== MAX_CLAUSES
)
392 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
393 p
->clause
[i2
+ 1] = 0;
394 if (insert_here
>= 0)
395 for (; i2
> insert_here
; i2
--)
396 p
->clause
[i2
] = p
->clause
[i2
- 1];
399 p
->clause
[insert_here
] = clause
;
405 static struct predicate
406 and_predicates (conditions conditions
,
407 struct predicate
*p
, struct predicate
*p2
)
409 struct predicate out
= *p
;
412 /* Avoid busy work. */
413 if (false_predicate_p (p2
) || true_predicate_p (p
))
415 if (false_predicate_p (p
) || true_predicate_p (p2
))
418 /* See how far predicates match. */
419 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
421 gcc_checking_assert (i
< MAX_CLAUSES
);
424 /* Combine the predicates rest. */
425 for (; p2
->clause
[i
]; i
++)
427 gcc_checking_assert (i
< MAX_CLAUSES
);
428 add_clause (conditions
, &out
, p2
->clause
[i
]);
434 /* Return true if predicates are obviously equal. */
437 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
440 for (i
= 0; p
->clause
[i
]; i
++)
442 gcc_checking_assert (i
< MAX_CLAUSES
);
443 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
444 gcc_checking_assert (!p2
->clause
[i
]
445 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
446 if (p
->clause
[i
] != p2
->clause
[i
])
449 return !p2
->clause
[i
];
455 static struct predicate
456 or_predicates (conditions conditions
,
457 struct predicate
*p
, struct predicate
*p2
)
459 struct predicate out
= true_predicate ();
462 /* Avoid busy work. */
463 if (false_predicate_p (p2
) || true_predicate_p (p
))
465 if (false_predicate_p (p
) || true_predicate_p (p2
))
467 if (predicates_equal_p (p
, p2
))
470 /* OK, combine the predicates. */
471 for (i
= 0; p
->clause
[i
]; i
++)
472 for (j
= 0; p2
->clause
[j
]; j
++)
474 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
475 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
481 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
482 if predicate P is known to be false. */
485 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
489 /* True remains true. */
490 if (true_predicate_p (p
))
493 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
495 /* See if we can find clause we can disprove. */
496 for (i
= 0; p
->clause
[i
]; i
++)
498 gcc_checking_assert (i
< MAX_CLAUSES
);
499 if (!(p
->clause
[i
] & possible_truths
))
505 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
506 instruction will be recomputed per invocation of the inlined call. */
509 predicate_probability (conditions conds
,
510 struct predicate
*p
, clause_t possible_truths
,
511 vec
<inline_param_summary
> inline_param_summary
)
514 int combined_prob
= REG_BR_PROB_BASE
;
516 /* True remains true. */
517 if (true_predicate_p (p
))
518 return REG_BR_PROB_BASE
;
520 if (false_predicate_p (p
))
523 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
525 /* See if we can find clause we can disprove. */
526 for (i
= 0; p
->clause
[i
]; i
++)
528 gcc_checking_assert (i
< MAX_CLAUSES
);
529 if (!(p
->clause
[i
] & possible_truths
))
535 if (!inline_param_summary
.exists ())
536 return REG_BR_PROB_BASE
;
537 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
538 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
540 if (i2
>= predicate_first_dynamic_condition
)
543 &(*conds
)[i2
- predicate_first_dynamic_condition
];
544 if (c
->code
== CHANGED
546 (int) inline_param_summary
.length ()))
549 inline_param_summary
[c
->operand_num
].change_prob
;
550 this_prob
= MAX (this_prob
, iprob
);
553 this_prob
= REG_BR_PROB_BASE
;
556 this_prob
= REG_BR_PROB_BASE
;
558 combined_prob
= MIN (this_prob
, combined_prob
);
563 return combined_prob
;
567 /* Dump conditional COND. */
570 dump_condition (FILE *f
, conditions conditions
, int cond
)
573 if (cond
== predicate_false_condition
)
574 fprintf (f
, "false");
575 else if (cond
== predicate_not_inlined_condition
)
576 fprintf (f
, "not inlined");
579 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
580 fprintf (f
, "op%i", c
->operand_num
);
582 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
583 c
->by_ref
? "ref " : "", c
->offset
);
584 if (c
->code
== IS_NOT_CONSTANT
)
586 fprintf (f
, " not constant");
589 if (c
->code
== CHANGED
)
591 fprintf (f
, " changed");
594 fprintf (f
, " %s ", op_symbol_code (c
->code
));
595 print_generic_expr (f
, c
->val
, 1);
600 /* Dump clause CLAUSE. */
603 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
610 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
611 if (clause
& (1 << i
))
616 dump_condition (f
, conds
, i
);
622 /* Dump predicate PREDICATE. */
625 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
628 if (true_predicate_p (pred
))
629 dump_clause (f
, conds
, 0);
631 for (i
= 0; pred
->clause
[i
]; i
++)
635 dump_clause (f
, conds
, pred
->clause
[i
]);
641 /* Dump inline hints. */
643 dump_inline_hints (FILE *f
, inline_hints hints
)
647 fprintf (f
, "inline hints:");
648 if (hints
& INLINE_HINT_indirect_call
)
650 hints
&= ~INLINE_HINT_indirect_call
;
651 fprintf (f
, " indirect_call");
653 if (hints
& INLINE_HINT_loop_iterations
)
655 hints
&= ~INLINE_HINT_loop_iterations
;
656 fprintf (f
, " loop_iterations");
658 if (hints
& INLINE_HINT_loop_stride
)
660 hints
&= ~INLINE_HINT_loop_stride
;
661 fprintf (f
, " loop_stride");
663 if (hints
& INLINE_HINT_same_scc
)
665 hints
&= ~INLINE_HINT_same_scc
;
666 fprintf (f
, " same_scc");
668 if (hints
& INLINE_HINT_in_scc
)
670 hints
&= ~INLINE_HINT_in_scc
;
671 fprintf (f
, " in_scc");
673 if (hints
& INLINE_HINT_cross_module
)
675 hints
&= ~INLINE_HINT_cross_module
;
676 fprintf (f
, " cross_module");
678 if (hints
& INLINE_HINT_declared_inline
)
680 hints
&= ~INLINE_HINT_declared_inline
;
681 fprintf (f
, " declared_inline");
683 if (hints
& INLINE_HINT_array_index
)
685 hints
&= ~INLINE_HINT_array_index
;
686 fprintf (f
, " array_index");
688 if (hints
& INLINE_HINT_known_hot
)
690 hints
&= ~INLINE_HINT_known_hot
;
691 fprintf (f
, " known_hot");
697 /* Record SIZE and TIME under condition PRED into the inline summary. */
700 account_size_time (struct inline_summary
*summary
, int size
, int time
,
701 struct predicate
*pred
)
707 if (false_predicate_p (pred
))
710 /* We need to create initial empty unconitional clause, but otherwie
711 we don't need to account empty times and sizes. */
712 if (!size
&& !time
&& summary
->entry
)
715 /* Watch overflow that might result from insane profiles. */
716 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
717 time
= MAX_TIME
* INLINE_TIME_SCALE
;
718 gcc_assert (time
>= 0);
720 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
721 if (predicates_equal_p (&e
->predicate
, pred
))
730 e
= &(*summary
->entry
)[0];
731 gcc_assert (!e
->predicate
.clause
[0]);
732 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
734 "\t\tReached limit on number of entries, "
735 "ignoring the predicate.");
737 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
740 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
741 ((double) size
) / INLINE_SIZE_SCALE
,
742 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
743 dump_predicate (dump_file
, summary
->conds
, pred
);
747 struct size_time_entry new_entry
;
748 new_entry
.size
= size
;
749 new_entry
.time
= time
;
750 new_entry
.predicate
= *pred
;
751 vec_safe_push (summary
->entry
, new_entry
);
757 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
758 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
762 /* Set predicate for edge E. */
765 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
767 struct inline_edge_summary
*es
= inline_edge_summary (e
);
769 /* If the edge is determined to be never executed, redirect it
770 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
771 if (predicate
&& false_predicate_p (predicate
) && e
->callee
)
773 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
775 e
->redirect_callee (cgraph_node::get_create
776 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
)));
777 e
->inline_failed
= CIF_UNREACHABLE
;
779 callee
->remove_symbol_and_inline_clones ();
781 if (predicate
&& !true_predicate_p (predicate
))
784 es
->predicate
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
785 *es
->predicate
= *predicate
;
790 pool_free (edge_predicate_pool
, es
->predicate
);
791 es
->predicate
= NULL
;
795 /* Set predicate for hint *P. */
798 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
800 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
803 pool_free (edge_predicate_pool
, *p
);
809 *p
= (struct predicate
*) pool_alloc (edge_predicate_pool
);
815 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
816 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
817 Return clause of possible truths. When INLINE_P is true, assume that we are
820 ERROR_MARK means compile time invariant. */
823 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
825 vec
<tree
> known_vals
,
826 vec
<ipa_agg_jump_function_p
>
829 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
830 struct inline_summary
*info
= inline_summary (node
);
834 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
839 /* We allow call stmt to have fewer arguments than the callee function
840 (especially for K&R style programs). So bound check here (we assume
841 known_aggs vector, if non-NULL, has the same length as
843 gcc_checking_assert (!known_aggs
.exists ()
844 || (known_vals
.length () == known_aggs
.length ()));
845 if (c
->operand_num
>= (int) known_vals
.length ())
847 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
853 struct ipa_agg_jump_function
*agg
;
855 if (c
->code
== CHANGED
857 && (known_vals
[c
->operand_num
] == error_mark_node
))
860 if (known_aggs
.exists ())
862 agg
= known_aggs
[c
->operand_num
];
863 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
870 val
= known_vals
[c
->operand_num
];
871 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
877 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
880 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
883 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
884 TYPE_SIZE (TREE_TYPE (val
)), 0))
886 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
889 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
892 if (res
&& integer_zerop (res
))
895 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
901 /* Work out what conditions might be true at invocation of E. */
904 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
905 clause_t
*clause_ptr
,
906 vec
<tree
> *known_vals_ptr
,
907 vec
<ipa_polymorphic_call_context
>
909 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
911 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
912 struct inline_summary
*info
= inline_summary (callee
);
913 vec
<tree
> known_vals
= vNULL
;
914 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
917 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
919 known_vals_ptr
->create (0);
920 if (known_contexts_ptr
)
921 known_contexts_ptr
->create (0);
923 if (ipa_node_params_vector
.exists ()
924 && !e
->call_stmt_cannot_inline_p
925 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
927 struct ipa_node_params
*parms_info
;
928 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
929 struct inline_edge_summary
*es
= inline_edge_summary (e
);
930 int i
, count
= ipa_get_cs_argument_count (args
);
932 if (e
->caller
->global
.inlined_to
)
933 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
935 parms_info
= IPA_NODE_REF (e
->caller
);
937 if (count
&& (info
->conds
|| known_vals_ptr
))
938 known_vals
.safe_grow_cleared (count
);
939 if (count
&& (info
->conds
|| known_aggs_ptr
))
940 known_aggs
.safe_grow_cleared (count
);
941 if (count
&& known_contexts_ptr
)
942 known_contexts_ptr
->safe_grow_cleared (count
);
944 for (i
= 0; i
< count
; i
++)
946 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
947 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
950 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
951 if (known_vals
.exists ())
954 else if (inline_p
&& !es
->param
[i
].change_prob
)
955 known_vals
[i
] = error_mark_node
;
957 if (known_contexts_ptr
)
958 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
960 /* TODO: When IPA-CP starts propagating and merging aggregate jump
961 functions, use its knowledge of the caller too, just like the
962 scalar case above. */
963 known_aggs
[i
] = &jf
->agg
;
968 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
969 known_vals
, known_aggs
);
972 *known_vals_ptr
= known_vals
;
974 known_vals
.release ();
977 *known_aggs_ptr
= known_aggs
;
979 known_aggs
.release ();
983 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
986 inline_summary_alloc (void)
988 if (!node_removal_hook_holder
)
989 node_removal_hook_holder
=
990 symtab
->add_cgraph_removal_hook (&inline_node_removal_hook
, NULL
);
991 if (!edge_removal_hook_holder
)
992 edge_removal_hook_holder
=
993 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
994 if (!node_duplication_hook_holder
)
995 node_duplication_hook_holder
=
996 symtab
->add_cgraph_duplication_hook (&inline_node_duplication_hook
, NULL
);
997 if (!edge_duplication_hook_holder
)
998 edge_duplication_hook_holder
=
999 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1001 if (vec_safe_length (inline_summary_vec
) <= (unsigned) symtab
->cgraph_max_uid
)
1002 vec_safe_grow_cleared (inline_summary_vec
, symtab
->cgraph_max_uid
+ 1);
1003 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1004 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1005 if (!edge_predicate_pool
)
1006 edge_predicate_pool
= create_alloc_pool ("edge predicates",
1007 sizeof (struct predicate
), 10);
1010 /* We are called multiple time for given function; clear
1011 data from previous run so they are not cumulated. */
1014 reset_inline_edge_summary (struct cgraph_edge
*e
)
1016 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1018 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1020 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1022 pool_free (edge_predicate_pool
, es
->predicate
);
1023 es
->predicate
= NULL
;
1024 es
->param
.release ();
1028 /* We are called multiple time for given function; clear
1029 data from previous run so they are not cumulated. */
1032 reset_inline_summary (struct cgraph_node
*node
)
1034 struct inline_summary
*info
= inline_summary (node
);
1035 struct cgraph_edge
*e
;
1037 info
->self_size
= info
->self_time
= 0;
1038 info
->estimated_stack_size
= 0;
1039 info
->estimated_self_stack_size
= 0;
1040 info
->stack_frame_offset
= 0;
1045 if (info
->loop_iterations
)
1047 pool_free (edge_predicate_pool
, info
->loop_iterations
);
1048 info
->loop_iterations
= NULL
;
1050 if (info
->loop_stride
)
1052 pool_free (edge_predicate_pool
, info
->loop_stride
);
1053 info
->loop_stride
= NULL
;
1055 if (info
->array_index
)
1057 pool_free (edge_predicate_pool
, info
->array_index
);
1058 info
->array_index
= NULL
;
1060 vec_free (info
->conds
);
1061 vec_free (info
->entry
);
1062 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1063 reset_inline_edge_summary (e
);
1064 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1065 reset_inline_edge_summary (e
);
1068 /* Hook that is called by cgraph.c when a node is removed. */
1071 inline_node_removal_hook (struct cgraph_node
*node
,
1072 void *data ATTRIBUTE_UNUSED
)
1074 struct inline_summary
*info
;
1075 if (vec_safe_length (inline_summary_vec
) <= (unsigned) node
->uid
)
1077 info
= inline_summary (node
);
1078 reset_inline_summary (node
);
1079 memset (info
, 0, sizeof (inline_summary_t
));
1082 /* Remap predicate P of former function to be predicate of duplicated function.
1083 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1084 INFO is inline summary of the duplicated node. */
1086 static struct predicate
1087 remap_predicate_after_duplication (struct predicate
*p
,
1088 clause_t possible_truths
,
1089 struct inline_summary
*info
)
1091 struct predicate new_predicate
= true_predicate ();
1093 for (j
= 0; p
->clause
[j
]; j
++)
1094 if (!(possible_truths
& p
->clause
[j
]))
1096 new_predicate
= false_predicate ();
1100 add_clause (info
->conds
, &new_predicate
,
1101 possible_truths
& p
->clause
[j
]);
1102 return new_predicate
;
1105 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1106 Additionally care about allocating new memory slot for updated predicate
1107 and set it to NULL when it becomes true or false (and thus uninteresting).
1111 remap_hint_predicate_after_duplication (struct predicate
**p
,
1112 clause_t possible_truths
,
1113 struct inline_summary
*info
)
1115 struct predicate new_predicate
;
1120 new_predicate
= remap_predicate_after_duplication (*p
,
1121 possible_truths
, info
);
1122 /* We do not want to free previous predicate; it is used by node origin. */
1124 set_hint_predicate (p
, new_predicate
);
1128 /* Hook that is called by cgraph.c when a node is duplicated. */
1131 inline_node_duplication_hook (struct cgraph_node
*src
,
1132 struct cgraph_node
*dst
,
1133 ATTRIBUTE_UNUSED
void *data
)
1135 struct inline_summary
*info
;
1136 inline_summary_alloc ();
1137 info
= inline_summary (dst
);
1138 memcpy (info
, inline_summary (src
), sizeof (struct inline_summary
));
1139 /* TODO: as an optimization, we may avoid copying conditions
1140 that are known to be false or true. */
1141 info
->conds
= vec_safe_copy (info
->conds
);
1143 /* When there are any replacements in the function body, see if we can figure
1144 out that something was optimized out. */
1145 if (ipa_node_params_vector
.exists () && dst
->clone
.tree_map
)
1147 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1148 /* Use SRC parm info since it may not be copied yet. */
1149 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1150 vec
<tree
> known_vals
= vNULL
;
1151 int count
= ipa_get_param_count (parms_info
);
1153 clause_t possible_truths
;
1154 struct predicate true_pred
= true_predicate ();
1156 int optimized_out_size
= 0;
1157 bool inlined_to_p
= false;
1158 struct cgraph_edge
*edge
;
1161 known_vals
.safe_grow_cleared (count
);
1162 for (i
= 0; i
< count
; i
++)
1164 struct ipa_replace_map
*r
;
1166 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1168 if (((!r
->old_tree
&& r
->parm_num
== i
)
1169 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1170 && r
->replace_p
&& !r
->ref_p
)
1172 known_vals
[i
] = r
->new_tree
;
1177 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1180 known_vals
.release ();
1182 account_size_time (info
, 0, 0, &true_pred
);
1184 /* Remap size_time vectors.
1185 Simplify the predicate by prunning out alternatives that are known
1187 TODO: as on optimization, we can also eliminate conditions known
1189 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1191 struct predicate new_predicate
;
1192 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1195 if (false_predicate_p (&new_predicate
))
1196 optimized_out_size
+= e
->size
;
1198 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1201 /* Remap edge predicates with the same simplification as above.
1202 Also copy constantness arrays. */
1203 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1205 struct predicate new_predicate
;
1206 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1208 if (!edge
->inline_failed
)
1209 inlined_to_p
= true;
1212 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1215 if (false_predicate_p (&new_predicate
)
1216 && !false_predicate_p (es
->predicate
))
1218 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1219 edge
->frequency
= 0;
1221 edge_set_predicate (edge
, &new_predicate
);
1224 /* Remap indirect edge predicates with the same simplificaiton as above.
1225 Also copy constantness arrays. */
1226 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1228 struct predicate new_predicate
;
1229 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1231 gcc_checking_assert (edge
->inline_failed
);
1234 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1237 if (false_predicate_p (&new_predicate
)
1238 && !false_predicate_p (es
->predicate
))
1240 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1241 edge
->frequency
= 0;
1243 edge_set_predicate (edge
, &new_predicate
);
1245 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1246 possible_truths
, info
);
1247 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1248 possible_truths
, info
);
1249 remap_hint_predicate_after_duplication (&info
->array_index
,
1250 possible_truths
, info
);
1252 /* If inliner or someone after inliner will ever start producing
1253 non-trivial clones, we will get trouble with lack of information
1254 about updating self sizes, because size vectors already contains
1255 sizes of the calees. */
1256 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1260 info
->entry
= vec_safe_copy (info
->entry
);
1261 if (info
->loop_iterations
)
1263 predicate p
= *info
->loop_iterations
;
1264 info
->loop_iterations
= NULL
;
1265 set_hint_predicate (&info
->loop_iterations
, p
);
1267 if (info
->loop_stride
)
1269 predicate p
= *info
->loop_stride
;
1270 info
->loop_stride
= NULL
;
1271 set_hint_predicate (&info
->loop_stride
, p
);
1273 if (info
->array_index
)
1275 predicate p
= *info
->array_index
;
1276 info
->array_index
= NULL
;
1277 set_hint_predicate (&info
->array_index
, p
);
1280 inline_update_overall_summary (dst
);
1284 /* Hook that is called by cgraph.c when a node is duplicated. */
1287 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1288 struct cgraph_edge
*dst
,
1289 ATTRIBUTE_UNUSED
void *data
)
1291 struct inline_edge_summary
*info
;
1292 struct inline_edge_summary
*srcinfo
;
1293 inline_summary_alloc ();
1294 info
= inline_edge_summary (dst
);
1295 srcinfo
= inline_edge_summary (src
);
1296 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1297 info
->predicate
= NULL
;
1298 edge_set_predicate (dst
, srcinfo
->predicate
);
1299 info
->param
= srcinfo
->param
.copy ();
1303 /* Keep edge cache consistent across edge removal. */
1306 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1307 void *data ATTRIBUTE_UNUSED
)
1309 if (edge_growth_cache
.exists ())
1310 reset_edge_growth_cache (edge
);
1311 reset_inline_edge_summary (edge
);
1315 /* Initialize growth caches. */
1318 initialize_growth_caches (void)
1320 if (symtab
->edges_max_uid
)
1321 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1322 if (symtab
->cgraph_max_uid
)
1323 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
1327 /* Free growth caches. */
1330 free_growth_caches (void)
1332 edge_growth_cache
.release ();
1333 node_growth_cache
.release ();
1337 /* Dump edge summaries associated to NODE and recursively to all clones.
1338 Indent by INDENT. */
1341 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1342 struct inline_summary
*info
)
1344 struct cgraph_edge
*edge
;
1345 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1347 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1348 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1352 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1353 " time: %2i callee size:%2i stack:%2i",
1354 indent
, "", callee
->name (), callee
->order
,
1355 !edge
->inline_failed
1356 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1357 indent
, "", es
->loop_depth
, edge
->frequency
,
1358 es
->call_stmt_size
, es
->call_stmt_time
,
1359 (int) inline_summary (callee
)->size
/ INLINE_SIZE_SCALE
,
1360 (int) inline_summary (callee
)->estimated_stack_size
);
1364 fprintf (f
, " predicate: ");
1365 dump_predicate (f
, info
->conds
, es
->predicate
);
1369 if (es
->param
.exists ())
1370 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1372 int prob
= es
->param
[i
].change_prob
;
1375 fprintf (f
, "%*s op%i is compile time invariant\n",
1377 else if (prob
!= REG_BR_PROB_BASE
)
1378 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1379 prob
* 100.0 / REG_BR_PROB_BASE
);
1381 if (!edge
->inline_failed
)
1383 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1384 " callee size %i\n",
1386 (int) inline_summary (callee
)->stack_frame_offset
,
1387 (int) inline_summary (callee
)->estimated_self_stack_size
,
1388 (int) inline_summary (callee
)->estimated_stack_size
);
1389 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1392 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1394 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1395 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1399 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1402 fprintf (f
, "predicate: ");
1403 dump_predicate (f
, info
->conds
, es
->predicate
);
1412 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1414 if (node
->definition
)
1416 struct inline_summary
*s
= inline_summary (node
);
1419 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1421 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1422 fprintf (f
, " always_inline");
1424 fprintf (f
, " inlinable");
1425 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1426 fprintf (f
, " global time: %i\n", s
->time
);
1427 fprintf (f
, " self size: %i\n", s
->self_size
);
1428 fprintf (f
, " global size: %i\n", s
->size
);
1429 fprintf (f
, " min size: %i\n", s
->min_size
);
1430 fprintf (f
, " self stack: %i\n",
1431 (int) s
->estimated_self_stack_size
);
1432 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1434 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1436 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1437 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1439 fprintf (f
, " size:%f, time:%f, predicate:",
1440 (double) e
->size
/ INLINE_SIZE_SCALE
,
1441 (double) e
->time
/ INLINE_TIME_SCALE
);
1442 dump_predicate (f
, s
->conds
, &e
->predicate
);
1444 if (s
->loop_iterations
)
1446 fprintf (f
, " loop iterations:");
1447 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1451 fprintf (f
, " loop stride:");
1452 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1456 fprintf (f
, " array index:");
1457 dump_predicate (f
, s
->conds
, s
->array_index
);
1459 fprintf (f
, " calls:\n");
1460 dump_inline_edge_summary (f
, 4, node
, s
);
1466 debug_inline_summary (struct cgraph_node
*node
)
1468 dump_inline_summary (stderr
, node
);
1472 dump_inline_summaries (FILE *f
)
1474 struct cgraph_node
*node
;
1476 FOR_EACH_DEFINED_FUNCTION (node
)
1477 if (!node
->global
.inlined_to
)
1478 dump_inline_summary (f
, node
);
1481 /* Give initial reasons why inlining would fail on EDGE. This gets either
1482 nullified or usually overwritten by more precise reasons later. */
1485 initialize_inline_failed (struct cgraph_edge
*e
)
1487 struct cgraph_node
*callee
= e
->callee
;
1489 if (e
->indirect_unknown_callee
)
1490 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1491 else if (!callee
->definition
)
1492 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1493 else if (callee
->local
.redefined_extern_inline
)
1494 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1495 else if (e
->call_stmt_cannot_inline_p
)
1496 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1497 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1498 /* We can't inline if the function is spawing a function. */
1499 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1501 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1504 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1505 boolean variable pointed to by DATA. */
1508 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1511 bool *b
= (bool *) data
;
1516 /* If OP refers to value of function parameter, return the corresponding
1520 unmodified_parm_1 (gimple stmt
, tree op
)
1522 /* SSA_NAME referring to parm default def? */
1523 if (TREE_CODE (op
) == SSA_NAME
1524 && SSA_NAME_IS_DEFAULT_DEF (op
)
1525 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1526 return SSA_NAME_VAR (op
);
1527 /* Non-SSA parm reference? */
1528 if (TREE_CODE (op
) == PARM_DECL
)
1530 bool modified
= false;
1533 ao_ref_init (&refd
, op
);
1534 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1542 /* If OP refers to value of function parameter, return the corresponding
1543 parameter. Also traverse chains of SSA register assignments. */
1546 unmodified_parm (gimple stmt
, tree op
)
1548 tree res
= unmodified_parm_1 (stmt
, op
);
1552 if (TREE_CODE (op
) == SSA_NAME
1553 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1554 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1555 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1556 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1560 /* If OP refers to a value of a function parameter or value loaded from an
1561 aggregate passed to a parameter (either by value or reference), return TRUE
1562 and store the number of the parameter to *INDEX_P and information whether
1563 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1564 the function parameters, STMT is the statement in which OP is used or
1568 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1569 gimple stmt
, tree op
, int *index_p
,
1570 struct agg_position_info
*aggpos
)
1572 tree res
= unmodified_parm_1 (stmt
, op
);
1574 gcc_checking_assert (aggpos
);
1577 *index_p
= ipa_get_param_decl_index (info
, res
);
1580 aggpos
->agg_contents
= false;
1581 aggpos
->by_ref
= false;
1585 if (TREE_CODE (op
) == SSA_NAME
)
1587 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1588 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1590 stmt
= SSA_NAME_DEF_STMT (op
);
1591 op
= gimple_assign_rhs1 (stmt
);
1592 if (!REFERENCE_CLASS_P (op
))
1593 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1597 aggpos
->agg_contents
= true;
1598 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1602 /* See if statement might disappear after inlining.
1603 0 - means not eliminated
1604 1 - half of statements goes away
1605 2 - for sure it is eliminated.
1606 We are not terribly sophisticated, basically looking for simple abstraction
1607 penalty wrappers. */
1610 eliminated_by_inlining_prob (gimple stmt
)
1612 enum gimple_code code
= gimple_code (stmt
);
1613 enum tree_code rhs_code
;
1623 if (gimple_num_ops (stmt
) != 2)
1626 rhs_code
= gimple_assign_rhs_code (stmt
);
1628 /* Casts of parameters, loads from parameters passed by reference
1629 and stores to return value or parameters are often free after
1630 inlining dua to SRA and further combining.
1631 Assume that half of statements goes away. */
1632 if (CONVERT_EXPR_CODE_P (rhs_code
)
1633 || rhs_code
== VIEW_CONVERT_EXPR
1634 || rhs_code
== ADDR_EXPR
1635 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1637 tree rhs
= gimple_assign_rhs1 (stmt
);
1638 tree lhs
= gimple_assign_lhs (stmt
);
1639 tree inner_rhs
= get_base_address (rhs
);
1640 tree inner_lhs
= get_base_address (lhs
);
1641 bool rhs_free
= false;
1642 bool lhs_free
= false;
1649 /* Reads of parameter are expected to be free. */
1650 if (unmodified_parm (stmt
, inner_rhs
))
1652 /* Match expressions of form &this->field. Those will most likely
1653 combine with something upstream after inlining. */
1654 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1656 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1657 if (TREE_CODE (op
) == PARM_DECL
)
1659 else if (TREE_CODE (op
) == MEM_REF
1660 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1664 /* When parameter is not SSA register because its address is taken
1665 and it is just copied into one, the statement will be completely
1666 free after inlining (we will copy propagate backward). */
1667 if (rhs_free
&& is_gimple_reg (lhs
))
1670 /* Reads of parameters passed by reference
1671 expected to be free (i.e. optimized out after inlining). */
1672 if (TREE_CODE (inner_rhs
) == MEM_REF
1673 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1676 /* Copying parameter passed by reference into gimple register is
1677 probably also going to copy propagate, but we can't be quite
1679 if (rhs_free
&& is_gimple_reg (lhs
))
1682 /* Writes to parameters, parameters passed by value and return value
1683 (either dirrectly or passed via invisible reference) are free.
1685 TODO: We ought to handle testcase like
1686 struct a {int a,b;};
1688 retrurnsturct (void)
1694 This translate into:
1709 For that we either need to copy ipa-split logic detecting writes
1711 if (TREE_CODE (inner_lhs
) == PARM_DECL
1712 || TREE_CODE (inner_lhs
) == RESULT_DECL
1713 || (TREE_CODE (inner_lhs
) == MEM_REF
1714 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1715 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1716 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1717 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1719 0))) == RESULT_DECL
))))
1722 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1724 if (lhs_free
&& rhs_free
)
1734 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1735 predicates to the CFG edges. */
1738 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1739 struct inline_summary
*summary
,
1745 struct agg_position_info aggpos
;
1746 enum tree_code code
, inverted_code
;
1752 last
= last_stmt (bb
);
1753 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1755 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1757 op
= gimple_cond_lhs (last
);
1758 /* TODO: handle conditionals like
1761 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1763 code
= gimple_cond_code (last
);
1764 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1766 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1768 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1769 ? code
: inverted_code
);
1770 /* invert_tree_comparison will return ERROR_MARK on FP
1771 comparsions that are not EQ/NE instead of returning proper
1772 unordered one. Be sure it is not confused with NON_CONSTANT. */
1773 if (this_code
!= ERROR_MARK
)
1775 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1777 gimple_cond_rhs (last
));
1778 e
->aux
= pool_alloc (edge_predicate_pool
);
1779 *(struct predicate
*) e
->aux
= p
;
1784 if (TREE_CODE (op
) != SSA_NAME
)
1787 if (builtin_constant_p (op))
1791 Here we can predicate nonconstant_code. We can't
1792 really handle constant_code since we have no predicate
1793 for this and also the constant code is not known to be
1794 optimized away when inliner doen't see operand is constant.
1795 Other optimizers might think otherwise. */
1796 if (gimple_cond_code (last
) != NE_EXPR
1797 || !integer_zerop (gimple_cond_rhs (last
)))
1799 set_stmt
= SSA_NAME_DEF_STMT (op
);
1800 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1801 || gimple_call_num_args (set_stmt
) != 1)
1803 op2
= gimple_call_arg (set_stmt
, 0);
1804 if (!unmodified_parm_or_parm_agg_item
1805 (info
, set_stmt
, op2
, &index
, &aggpos
))
1807 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1809 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1810 IS_NOT_CONSTANT
, NULL_TREE
);
1811 e
->aux
= pool_alloc (edge_predicate_pool
);
1812 *(struct predicate
*) e
->aux
= p
;
1817 /* If BB ends by a switch we can turn into predicates, attach corresponding
1818 predicates to the CFG edges. */
1821 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1822 struct inline_summary
*summary
,
1828 struct agg_position_info aggpos
;
1834 lastg
= last_stmt (bb
);
1835 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1837 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1838 op
= gimple_switch_index (last
);
1839 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1842 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1844 e
->aux
= pool_alloc (edge_predicate_pool
);
1845 *(struct predicate
*) e
->aux
= false_predicate ();
1847 n
= gimple_switch_num_labels (last
);
1848 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1850 tree cl
= gimple_switch_label (last
, case_idx
);
1854 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1855 min
= CASE_LOW (cl
);
1856 max
= CASE_HIGH (cl
);
1858 /* For default we might want to construct predicate that none
1859 of cases is met, but it is bit hard to do not having negations
1860 of conditionals handy. */
1862 p
= true_predicate ();
1864 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1867 struct predicate p1
, p2
;
1868 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1869 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1870 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1872 *(struct predicate
*) e
->aux
1873 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1878 /* For each BB in NODE attach to its AUX pointer predicate under
1879 which it is executable. */
1882 compute_bb_predicates (struct cgraph_node
*node
,
1883 struct ipa_node_params
*parms_info
,
1884 struct inline_summary
*summary
)
1886 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1890 FOR_EACH_BB_FN (bb
, my_function
)
1892 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1893 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1896 /* Entry block is always executable. */
1897 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1898 = pool_alloc (edge_predicate_pool
);
1899 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1900 = true_predicate ();
1902 /* A simple dataflow propagation of predicates forward in the CFG.
1903 TODO: work in reverse postorder. */
1907 FOR_EACH_BB_FN (bb
, my_function
)
1909 struct predicate p
= false_predicate ();
1912 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1916 struct predicate this_bb_predicate
1917 = *(struct predicate
*) e
->src
->aux
;
1920 = and_predicates (summary
->conds
, &this_bb_predicate
,
1921 (struct predicate
*) e
->aux
);
1922 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1923 if (true_predicate_p (&p
))
1927 if (false_predicate_p (&p
))
1928 gcc_assert (!bb
->aux
);
1934 bb
->aux
= pool_alloc (edge_predicate_pool
);
1935 *((struct predicate
*) bb
->aux
) = p
;
1937 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1939 /* This OR operation is needed to ensure monotonous data flow
1940 in the case we hit the limit on number of clauses and the
1941 and/or operations above give approximate answers. */
1942 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1943 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1946 *((struct predicate
*) bb
->aux
) = p
;
1955 /* We keep info about constantness of SSA names. */
1957 typedef struct predicate predicate_t
;
1958 /* Return predicate specifying when the STMT might have result that is not
1959 a compile time constant. */
1961 static struct predicate
1962 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1963 struct inline_summary
*summary
,
1965 vec
<predicate_t
> nonconstant_names
)
1970 while (UNARY_CLASS_P (expr
))
1971 expr
= TREE_OPERAND (expr
, 0);
1973 parm
= unmodified_parm (NULL
, expr
);
1974 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1975 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1976 if (is_gimple_min_invariant (expr
))
1977 return false_predicate ();
1978 if (TREE_CODE (expr
) == SSA_NAME
)
1979 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1980 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1982 struct predicate p1
= will_be_nonconstant_expr_predicate
1983 (info
, summary
, TREE_OPERAND (expr
, 0),
1985 struct predicate p2
;
1986 if (true_predicate_p (&p1
))
1988 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1989 TREE_OPERAND (expr
, 1),
1991 return or_predicates (summary
->conds
, &p1
, &p2
);
1993 else if (TREE_CODE (expr
) == COND_EXPR
)
1995 struct predicate p1
= will_be_nonconstant_expr_predicate
1996 (info
, summary
, TREE_OPERAND (expr
, 0),
1998 struct predicate p2
;
1999 if (true_predicate_p (&p1
))
2001 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2002 TREE_OPERAND (expr
, 1),
2004 if (true_predicate_p (&p2
))
2006 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2007 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2008 TREE_OPERAND (expr
, 2),
2010 return or_predicates (summary
->conds
, &p1
, &p2
);
2017 return false_predicate ();
2021 /* Return predicate specifying when the STMT might have result that is not
2022 a compile time constant. */
2024 static struct predicate
2025 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2026 struct inline_summary
*summary
,
2028 vec
<predicate_t
> nonconstant_names
)
2030 struct predicate p
= true_predicate ();
2033 struct predicate op_non_const
;
2036 struct agg_position_info aggpos
;
2038 /* What statments might be optimized away
2039 when their arguments are constant. */
2040 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2041 && gimple_code (stmt
) != GIMPLE_COND
2042 && gimple_code (stmt
) != GIMPLE_SWITCH
2043 && (gimple_code (stmt
) != GIMPLE_CALL
2044 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2047 /* Stores will stay anyway. */
2048 if (gimple_store_p (stmt
))
2051 is_load
= gimple_assign_load_p (stmt
);
2053 /* Loads can be optimized when the value is known. */
2057 gcc_assert (gimple_assign_single_p (stmt
));
2058 op
= gimple_assign_rhs1 (stmt
);
2059 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2066 /* See if we understand all operands before we start
2067 adding conditionals. */
2068 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2070 tree parm
= unmodified_parm (stmt
, use
);
2071 /* For arguments we can build a condition. */
2072 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2074 if (TREE_CODE (use
) != SSA_NAME
)
2076 /* If we know when operand is constant,
2077 we still can say something useful. */
2078 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2085 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2087 op_non_const
= false_predicate ();
2088 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2090 tree parm
= unmodified_parm (stmt
, use
);
2093 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2095 if (index
!= base_index
)
2096 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2101 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2102 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2104 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2105 && gimple_op (stmt
, 0)
2106 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2107 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2109 return op_non_const
;
2112 struct record_modified_bb_info
2118 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2119 set except for info->stmt. */
2122 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2124 struct record_modified_bb_info
*info
=
2125 (struct record_modified_bb_info
*) data
;
2126 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2128 bitmap_set_bit (info
->bb_set
,
2129 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2130 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2131 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2135 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2136 will change since last invocation of STMT.
2138 Value 0 is reserved for compile time invariants.
2139 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2140 ought to be REG_BR_PROB_BASE / estimated_iters. */
2143 param_change_prob (gimple stmt
, int i
)
2145 tree op
= gimple_call_arg (stmt
, i
);
2146 basic_block bb
= gimple_bb (stmt
);
2149 /* Global invariants neve change. */
2150 if (is_gimple_min_invariant (op
))
2152 /* We would have to do non-trivial analysis to really work out what
2153 is the probability of value to change (i.e. when init statement
2154 is in a sibling loop of the call).
2156 We do an conservative estimate: when call is executed N times more often
2157 than the statement defining value, we take the frequency 1/N. */
2158 if (TREE_CODE (op
) == SSA_NAME
)
2163 return REG_BR_PROB_BASE
;
2165 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2166 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2168 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2172 if (init_freq
< bb
->frequency
)
2173 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2175 return REG_BR_PROB_BASE
;
2178 base
= get_base_address (op
);
2183 struct record_modified_bb_info info
;
2186 tree init
= ctor_for_folding (base
);
2188 if (init
!= error_mark_node
)
2191 return REG_BR_PROB_BASE
;
2192 ao_ref_init (&refd
, op
);
2194 info
.bb_set
= BITMAP_ALLOC (NULL
);
2195 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2197 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2199 BITMAP_FREE (info
.bb_set
);
2200 return REG_BR_PROB_BASE
;
2203 /* Assume that every memory is initialized at entry.
2204 TODO: Can we easilly determine if value is always defined
2205 and thus we may skip entry block? */
2206 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2207 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2211 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2212 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2214 BITMAP_FREE (info
.bb_set
);
2215 if (max
< bb
->frequency
)
2216 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2218 return REG_BR_PROB_BASE
;
2220 return REG_BR_PROB_BASE
;
2223 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2224 sub-graph and if the predicate the condition depends on is known. If so,
2225 return true and store the pointer the predicate in *P. */
2228 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2229 struct inline_summary
*summary
, basic_block bb
,
2230 struct predicate
*p
,
2231 vec
<predicate_t
> nonconstant_names
)
2235 basic_block first_bb
= NULL
;
2238 if (single_pred_p (bb
))
2240 *p
= false_predicate ();
2244 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2246 if (single_succ_p (e
->src
))
2248 if (!single_pred_p (e
->src
))
2251 first_bb
= single_pred (e
->src
);
2252 else if (single_pred (e
->src
) != first_bb
)
2259 else if (e
->src
!= first_bb
)
2267 stmt
= last_stmt (first_bb
);
2269 || gimple_code (stmt
) != GIMPLE_COND
2270 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2273 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2274 gimple_cond_lhs (stmt
),
2276 if (true_predicate_p (p
))
2282 /* Given a PHI statement in a function described by inline properties SUMMARY
2283 and *P being the predicate describing whether the selected PHI argument is
2284 known, store a predicate for the result of the PHI statement into
2285 NONCONSTANT_NAMES, if possible. */
2288 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2289 struct predicate
*p
,
2290 vec
<predicate_t
> nonconstant_names
)
2294 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2296 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2297 if (!is_gimple_min_invariant (arg
))
2299 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2300 *p
= or_predicates (summary
->conds
, p
,
2301 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2302 if (true_predicate_p (p
))
2307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2309 fprintf (dump_file
, "\t\tphi predicate: ");
2310 dump_predicate (dump_file
, summary
->conds
, p
);
2312 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2315 /* Return predicate specifying when array index in access OP becomes non-constant. */
2317 static struct predicate
2318 array_index_predicate (struct inline_summary
*info
,
2319 vec
< predicate_t
> nonconstant_names
, tree op
)
2321 struct predicate p
= false_predicate ();
2322 while (handled_component_p (op
))
2324 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2326 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2327 p
= or_predicates (info
->conds
, &p
,
2328 &nonconstant_names
[SSA_NAME_VERSION
2329 (TREE_OPERAND (op
, 1))]);
2331 op
= TREE_OPERAND (op
, 0);
2336 /* For a typical usage of __builtin_expect (a<b, 1), we
2337 may introduce an extra relation stmt:
2338 With the builtin, we have
2341 t3 = __builtin_expect (t2, 1);
2344 Without the builtin, we have
2347 This affects the size/time estimation and may have
2348 an impact on the earlier inlining.
2349 Here find this pattern and fix it up later. */
2352 find_foldable_builtin_expect (basic_block bb
)
2354 gimple_stmt_iterator bsi
;
2356 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2358 gimple stmt
= gsi_stmt (bsi
);
2359 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2360 || (is_gimple_call (stmt
)
2361 && gimple_call_internal_p (stmt
)
2362 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2364 tree var
= gimple_call_lhs (stmt
);
2365 tree arg
= gimple_call_arg (stmt
, 0);
2366 use_operand_p use_p
;
2373 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2375 while (TREE_CODE (arg
) == SSA_NAME
)
2377 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2378 if (!is_gimple_assign (stmt_tmp
))
2380 switch (gimple_assign_rhs_code (stmt_tmp
))
2399 arg
= gimple_assign_rhs1 (stmt_tmp
);
2402 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2403 && gimple_code (use_stmt
) == GIMPLE_COND
)
2410 /* Return true when the basic blocks contains only clobbers followed by RESX.
2411 Such BBs are kept around to make removal of dead stores possible with
2412 presence of EH and will be optimized out by optimize_clobbers later in the
2415 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2416 that can be clobber only, too.. When it is false, the RESX is not necessary
2417 on the end of basic block. */
2420 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2422 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2428 if (gsi_end_p (gsi
))
2430 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2434 else if (!single_succ_p (bb
))
2437 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2439 gimple stmt
= gsi_stmt (gsi
);
2440 if (is_gimple_debug (stmt
))
2442 if (gimple_clobber_p (stmt
))
2444 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2449 /* See if all predecestors are either throws or clobber only BBs. */
2450 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2451 if (!(e
->flags
& EDGE_EH
)
2452 && !clobber_only_eh_bb_p (e
->src
, false))
2458 /* Compute function body size parameters for NODE.
2459 When EARLY is true, we compute only simple summaries without
2460 non-trivial predicates to drive the early inliner. */
2463 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2466 /* Estimate static overhead for function prologue/epilogue and alignment. */
2468 /* Benefits are scaled by probability of elimination that is in range
2471 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2473 struct inline_summary
*info
= inline_summary (node
);
2474 struct predicate bb_predicate
;
2475 struct ipa_node_params
*parms_info
= NULL
;
2476 vec
<predicate_t
> nonconstant_names
= vNULL
;
2479 predicate array_index
= true_predicate ();
2480 gimple fix_builtin_expect_stmt
;
2485 if (opt_for_fn (node
->decl
, optimize
) && !early
)
2487 calculate_dominance_info (CDI_DOMINATORS
);
2488 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2490 if (ipa_node_params_vector
.exists ())
2492 parms_info
= IPA_NODE_REF (node
);
2493 nonconstant_names
.safe_grow_cleared
2494 (SSANAMES (my_function
)->length ());
2499 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2502 /* When we run into maximal number of entries, we assign everything to the
2503 constant truth case. Be sure to have it in list. */
2504 bb_predicate
= true_predicate ();
2505 account_size_time (info
, 0, 0, &bb_predicate
);
2507 bb_predicate
= not_inlined_predicate ();
2508 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2510 gcc_assert (my_function
&& my_function
->cfg
);
2512 compute_bb_predicates (node
, parms_info
, info
);
2513 gcc_assert (cfun
== my_function
);
2514 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2515 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2516 for (n
= 0; n
< nblocks
; n
++)
2518 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2519 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2520 if (clobber_only_eh_bb_p (bb
))
2522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2523 fprintf (dump_file
, "\n Ignoring BB %i;"
2524 " it will be optimized away by cleanup_clobbers\n",
2529 /* TODO: Obviously predicates can be propagated down across CFG. */
2533 bb_predicate
= *(struct predicate
*) bb
->aux
;
2535 bb_predicate
= false_predicate ();
2538 bb_predicate
= true_predicate ();
2540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2542 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2543 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2546 if (parms_info
&& nonconstant_names
.exists ())
2548 struct predicate phi_predicate
;
2549 bool first_phi
= true;
2551 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2555 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2562 fprintf (dump_file
, " ");
2563 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2565 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2570 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2572 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2575 gimple stmt
= gsi_stmt (bsi
);
2576 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2577 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2579 struct predicate will_be_nonconstant
;
2581 /* This relation stmt should be folded after we remove
2582 buildin_expect call. Adjust the cost here. */
2583 if (stmt
== fix_builtin_expect_stmt
)
2589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2591 fprintf (dump_file
, " ");
2592 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2593 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2594 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2598 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2600 struct predicate this_array_index
;
2602 array_index_predicate (info
, nonconstant_names
,
2603 gimple_assign_rhs1 (stmt
));
2604 if (!false_predicate_p (&this_array_index
))
2606 and_predicates (info
->conds
, &array_index
,
2609 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2611 struct predicate this_array_index
;
2613 array_index_predicate (info
, nonconstant_names
,
2614 gimple_get_lhs (stmt
));
2615 if (!false_predicate_p (&this_array_index
))
2617 and_predicates (info
->conds
, &array_index
,
2622 if (is_gimple_call (stmt
)
2623 && !gimple_call_internal_p (stmt
))
2625 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2626 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2628 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2629 resolved as constant. We however don't want to optimize
2630 out the cgraph edges. */
2631 if (nonconstant_names
.exists ()
2632 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2633 && gimple_call_lhs (stmt
)
2634 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2636 struct predicate false_p
= false_predicate ();
2637 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2640 if (ipa_node_params_vector
.exists ())
2642 int count
= gimple_call_num_args (stmt
);
2646 es
->param
.safe_grow_cleared (count
);
2647 for (i
= 0; i
< count
; i
++)
2649 int prob
= param_change_prob (stmt
, i
);
2650 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2651 es
->param
[i
].change_prob
= prob
;
2655 es
->call_stmt_size
= this_size
;
2656 es
->call_stmt_time
= this_time
;
2657 es
->loop_depth
= bb_loop_depth (bb
);
2658 edge_set_predicate (edge
, &bb_predicate
);
2661 /* TODO: When conditional jump or swithc is known to be constant, but
2662 we did not translate it into the predicates, we really can account
2663 just maximum of the possible paths. */
2666 = will_be_nonconstant_predicate (parms_info
, info
,
2667 stmt
, nonconstant_names
);
2668 if (this_time
|| this_size
)
2674 prob
= eliminated_by_inlining_prob (stmt
);
2675 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2677 "\t\t50%% will be eliminated by inlining\n");
2678 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2679 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2682 p
= and_predicates (info
->conds
, &bb_predicate
,
2683 &will_be_nonconstant
);
2685 p
= true_predicate ();
2687 if (!false_predicate_p (&p
)
2688 || (is_gimple_call (stmt
)
2689 && !false_predicate_p (&bb_predicate
)))
2693 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2694 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2697 /* We account everything but the calls. Calls have their own
2698 size/time info attached to cgraph edges. This is necessary
2699 in order to make the cost disappear after inlining. */
2700 if (!is_gimple_call (stmt
))
2704 struct predicate ip
= not_inlined_predicate ();
2705 ip
= and_predicates (info
->conds
, &ip
, &p
);
2706 account_size_time (info
, this_size
* prob
,
2707 this_time
* prob
, &ip
);
2710 account_size_time (info
, this_size
* (2 - prob
),
2711 this_time
* (2 - prob
), &p
);
2714 gcc_assert (time
>= 0);
2715 gcc_assert (size
>= 0);
2719 set_hint_predicate (&inline_summary (node
)->array_index
, array_index
);
2720 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2721 if (time
> MAX_TIME
)
2725 if (!early
&& nonconstant_names
.exists ())
2728 predicate loop_iterations
= true_predicate ();
2729 predicate loop_stride
= true_predicate ();
2731 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2732 flow_loops_dump (dump_file
, NULL
, 0);
2734 FOR_EACH_LOOP (loop
, 0)
2739 struct tree_niter_desc niter_desc
;
2740 basic_block
*body
= get_loop_body (loop
);
2741 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2743 exits
= get_loop_exit_edges (loop
);
2744 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2745 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2746 && !is_gimple_min_invariant (niter_desc
.niter
))
2748 predicate will_be_nonconstant
2749 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2752 if (!true_predicate_p (&will_be_nonconstant
))
2753 will_be_nonconstant
= and_predicates (info
->conds
,
2755 &will_be_nonconstant
);
2756 if (!true_predicate_p (&will_be_nonconstant
)
2757 && !false_predicate_p (&will_be_nonconstant
))
2758 /* This is slightly inprecise. We may want to represent each
2759 loop with independent predicate. */
2761 and_predicates (info
->conds
, &loop_iterations
,
2762 &will_be_nonconstant
);
2766 for (i
= 0; i
< loop
->num_nodes
; i
++)
2768 gimple_stmt_iterator gsi
;
2769 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2770 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2773 gimple stmt
= gsi_stmt (gsi
);
2778 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2780 predicate will_be_nonconstant
;
2783 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2784 || is_gimple_min_invariant (iv
.step
))
2787 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2790 if (!true_predicate_p (&will_be_nonconstant
))
2792 = and_predicates (info
->conds
,
2794 &will_be_nonconstant
);
2795 if (!true_predicate_p (&will_be_nonconstant
)
2796 && !false_predicate_p (&will_be_nonconstant
))
2797 /* This is slightly inprecise. We may want to represent
2798 each loop with independent predicate. */
2800 and_predicates (info
->conds
, &loop_stride
,
2801 &will_be_nonconstant
);
2807 set_hint_predicate (&inline_summary (node
)->loop_iterations
,
2809 set_hint_predicate (&inline_summary (node
)->loop_stride
, loop_stride
);
2812 FOR_ALL_BB_FN (bb
, my_function
)
2818 pool_free (edge_predicate_pool
, bb
->aux
);
2820 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2823 pool_free (edge_predicate_pool
, e
->aux
);
2827 inline_summary (node
)->self_time
= time
;
2828 inline_summary (node
)->self_size
= size
;
2829 nonconstant_names
.release ();
2830 if (opt_for_fn (node
->decl
, optimize
) && !early
)
2832 loop_optimizer_finalize ();
2833 free_dominance_info (CDI_DOMINATORS
);
2837 fprintf (dump_file
, "\n");
2838 dump_inline_summary (dump_file
, node
);
2843 /* Compute parameters of functions used by inliner.
2844 EARLY is true when we compute parameters for the early inliner */
2847 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2849 HOST_WIDE_INT self_stack_size
;
2850 struct cgraph_edge
*e
;
2851 struct inline_summary
*info
;
2853 gcc_assert (!node
->global
.inlined_to
);
2855 inline_summary_alloc ();
2857 info
= inline_summary (node
);
2858 reset_inline_summary (node
);
2860 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2861 Once this happen, we will need to more curefully predict call
2863 if (node
->thunk
.thunk_p
)
2865 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2866 struct predicate t
= true_predicate ();
2868 info
->inlinable
= 0;
2869 node
->callees
->call_stmt_cannot_inline_p
= true;
2870 node
->local
.can_change_signature
= false;
2871 es
->call_stmt_time
= 1;
2872 es
->call_stmt_size
= 1;
2873 account_size_time (info
, 0, 0, &t
);
2877 /* Even is_gimple_min_invariant rely on current_function_decl. */
2878 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2880 /* Estimate the stack size for the function if we're optimizing. */
2881 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2882 info
->estimated_self_stack_size
= self_stack_size
;
2883 info
->estimated_stack_size
= self_stack_size
;
2884 info
->stack_frame_offset
= 0;
2886 /* Can this function be inlined at all? */
2887 if (!opt_for_fn (node
->decl
, optimize
)
2888 && !lookup_attribute ("always_inline",
2889 DECL_ATTRIBUTES (node
->decl
)))
2890 info
->inlinable
= false;
2892 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2894 /* Type attributes can use parameter indices to describe them. */
2895 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2896 node
->local
.can_change_signature
= false;
2899 /* Otherwise, inlinable functions always can change signature. */
2900 if (info
->inlinable
)
2901 node
->local
.can_change_signature
= true;
2904 /* Functions calling builtin_apply can not change signature. */
2905 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2907 tree
cdecl = e
->callee
->decl
;
2908 if (DECL_BUILT_IN (cdecl)
2909 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2910 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2911 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2914 node
->local
.can_change_signature
= !e
;
2917 estimate_function_body_sizes (node
, early
);
2919 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2920 if (e
->callee
->comdat_local_p ())
2922 node
->calls_comdat_local
= (e
!= NULL
);
2924 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2925 info
->time
= info
->self_time
;
2926 info
->size
= info
->self_size
;
2927 info
->stack_frame_offset
= 0;
2928 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2929 #ifdef ENABLE_CHECKING
2930 inline_update_overall_summary (node
);
2931 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2938 /* Compute parameters of functions used by inliner using
2939 current_function_decl. */
2942 compute_inline_parameters_for_current (void)
2944 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2950 const pass_data pass_data_inline_parameters
=
2952 GIMPLE_PASS
, /* type */
2953 "inline_param", /* name */
2954 OPTGROUP_INLINE
, /* optinfo_flags */
2955 TV_INLINE_PARAMETERS
, /* tv_id */
2956 0, /* properties_required */
2957 0, /* properties_provided */
2958 0, /* properties_destroyed */
2959 0, /* todo_flags_start */
2960 0, /* todo_flags_finish */
2963 class pass_inline_parameters
: public gimple_opt_pass
2966 pass_inline_parameters (gcc::context
*ctxt
)
2967 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
2970 /* opt_pass methods: */
2971 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
2972 virtual unsigned int execute (function
*)
2974 return compute_inline_parameters_for_current ();
2977 }; // class pass_inline_parameters
2982 make_pass_inline_parameters (gcc::context
*ctxt
)
2984 return new pass_inline_parameters (ctxt
);
2988 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
2989 KNOWN_CONTEXTS and KNOWN_AGGS. */
2992 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
2993 int *size
, int *time
,
2994 vec
<tree
> known_vals
,
2995 vec
<ipa_polymorphic_call_context
> known_contexts
,
2996 vec
<ipa_agg_jump_function_p
> known_aggs
)
2999 struct cgraph_node
*callee
;
3000 struct inline_summary
*isummary
;
3001 enum availability avail
;
3004 if (!known_vals
.exists () && !known_contexts
.exists ())
3006 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3009 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3010 known_aggs
, &speculative
);
3011 if (!target
|| speculative
)
3014 /* Account for difference in cost between indirect and direct calls. */
3015 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3016 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3017 gcc_checking_assert (*time
>= 0);
3018 gcc_checking_assert (*size
>= 0);
3020 callee
= cgraph_node::get (target
);
3021 if (!callee
|| !callee
->definition
)
3023 callee
= callee
->function_symbol (&avail
);
3024 if (avail
< AVAIL_AVAILABLE
)
3026 isummary
= inline_summary (callee
);
3027 return isummary
->inlinable
;
3030 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3031 handle edge E with probability PROB.
3032 Set HINTS if edge may be devirtualized.
3033 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3037 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3040 vec
<tree
> known_vals
,
3041 vec
<ipa_polymorphic_call_context
> known_contexts
,
3042 vec
<ipa_agg_jump_function_p
> known_aggs
,
3043 inline_hints
*hints
)
3045 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3046 int call_size
= es
->call_stmt_size
;
3047 int call_time
= es
->call_stmt_time
;
3050 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3051 known_vals
, known_contexts
, known_aggs
)
3052 && hints
&& e
->maybe_hot_p ())
3053 *hints
|= INLINE_HINT_indirect_call
;
3054 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3057 *min_size
+= cur_size
;
3058 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3059 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3060 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3061 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3066 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3067 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3068 describe context of the call site. */
3071 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3072 int *min_size
, int *time
,
3073 inline_hints
*hints
,
3074 clause_t possible_truths
,
3075 vec
<tree
> known_vals
,
3076 vec
<ipa_polymorphic_call_context
> known_contexts
,
3077 vec
<ipa_agg_jump_function_p
> known_aggs
)
3079 struct cgraph_edge
*e
;
3080 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3082 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3084 || evaluate_predicate (es
->predicate
, possible_truths
))
3086 if (e
->inline_failed
)
3088 /* Predicates of calls shall not use NOT_CHANGED codes,
3089 sowe do not need to compute probabilities. */
3090 estimate_edge_size_and_time (e
, size
,
3091 es
->predicate
? NULL
: min_size
,
3092 time
, REG_BR_PROB_BASE
,
3093 known_vals
, known_contexts
,
3097 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3100 known_vals
, known_contexts
,
3104 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3106 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3108 || evaluate_predicate (es
->predicate
, possible_truths
))
3109 estimate_edge_size_and_time (e
, size
,
3110 es
->predicate
? NULL
: min_size
,
3111 time
, REG_BR_PROB_BASE
,
3112 known_vals
, known_contexts
, known_aggs
,
3118 /* Estimate size and time needed to execute NODE assuming
3119 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3120 information about NODE's arguments. If non-NULL use also probability
3121 information present in INLINE_PARAM_SUMMARY vector.
3122 Additionally detemine hints determined by the context. Finally compute
3123 minimal size needed for the call that is independent on the call context and
3124 can be used for fast estimates. Return the values in RET_SIZE,
3125 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3128 estimate_node_size_and_time (struct cgraph_node
*node
,
3129 clause_t possible_truths
,
3130 vec
<tree
> known_vals
,
3131 vec
<ipa_polymorphic_call_context
> known_contexts
,
3132 vec
<ipa_agg_jump_function_p
> known_aggs
,
3133 int *ret_size
, int *ret_min_size
, int *ret_time
,
3134 inline_hints
*ret_hints
,
3135 vec
<inline_param_summary
>
3136 inline_param_summary
)
3138 struct inline_summary
*info
= inline_summary (node
);
3143 inline_hints hints
= 0;
3146 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3149 fprintf (dump_file
, " Estimating body: %s/%i\n"
3150 " Known to be false: ", node
->name (),
3153 for (i
= predicate_not_inlined_condition
;
3154 i
< (predicate_first_dynamic_condition
3155 + (int) vec_safe_length (info
->conds
)); i
++)
3156 if (!(possible_truths
& (1 << i
)))
3159 fprintf (dump_file
, ", ");
3161 dump_condition (dump_file
, info
->conds
, i
);
3165 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3166 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3169 gcc_checking_assert (e
->time
>= 0);
3170 gcc_checking_assert (time
>= 0);
3171 if (!inline_param_summary
.exists ())
3175 int prob
= predicate_probability (info
->conds
,
3178 inline_param_summary
);
3179 gcc_checking_assert (prob
>= 0);
3180 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3181 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3183 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3184 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3185 gcc_checking_assert (time
>= 0);
3188 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3189 min_size
= (*info
->entry
)[0].size
;
3190 gcc_checking_assert (size
>= 0);
3191 gcc_checking_assert (time
>= 0);
3193 if (info
->loop_iterations
3194 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3195 hints
|= INLINE_HINT_loop_iterations
;
3196 if (info
->loop_stride
3197 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3198 hints
|= INLINE_HINT_loop_stride
;
3199 if (info
->array_index
3200 && !evaluate_predicate (info
->array_index
, possible_truths
))
3201 hints
|= INLINE_HINT_array_index
;
3203 hints
|= INLINE_HINT_in_scc
;
3204 if (DECL_DECLARED_INLINE_P (node
->decl
))
3205 hints
|= INLINE_HINT_declared_inline
;
3207 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3208 known_vals
, known_contexts
, known_aggs
);
3209 gcc_checking_assert (size
>= 0);
3210 gcc_checking_assert (time
>= 0);
3211 time
= RDIV (time
, INLINE_TIME_SCALE
);
3212 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3213 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3215 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3216 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3222 *ret_min_size
= min_size
;
3229 /* Estimate size and time needed to execute callee of EDGE assuming that
3230 parameters known to be constant at caller of EDGE are propagated.
3231 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3232 and types for parameters. */
3235 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3236 vec
<tree
> known_vals
,
3237 vec
<ipa_polymorphic_call_context
>
3239 vec
<ipa_agg_jump_function_p
> known_aggs
,
3240 int *ret_size
, int *ret_time
,
3241 inline_hints
*hints
)
3245 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3247 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3248 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3251 /* Translate all conditions from callee representation into caller
3252 representation and symbolically evaluate predicate P into new predicate.
3254 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3255 is summary of function predicate P is from. OPERAND_MAP is array giving
3256 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3257 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3258 predicate under which callee is executed. OFFSET_MAP is an array of of
3259 offsets that need to be added to conditions, negative offset means that
3260 conditions relying on values passed by reference have to be discarded
3261 because they might not be preserved (and should be considered offset zero
3262 for other purposes). */
3264 static struct predicate
3265 remap_predicate (struct inline_summary
*info
,
3266 struct inline_summary
*callee_info
,
3267 struct predicate
*p
,
3268 vec
<int> operand_map
,
3269 vec
<int> offset_map
,
3270 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3273 struct predicate out
= true_predicate ();
3275 /* True predicate is easy. */
3276 if (true_predicate_p (p
))
3277 return *toplev_predicate
;
3278 for (i
= 0; p
->clause
[i
]; i
++)
3280 clause_t clause
= p
->clause
[i
];
3282 struct predicate clause_predicate
= false_predicate ();
3284 gcc_assert (i
< MAX_CLAUSES
);
3286 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3287 /* Do we have condition we can't disprove? */
3288 if (clause
& possible_truths
& (1 << cond
))
3290 struct predicate cond_predicate
;
3291 /* Work out if the condition can translate to predicate in the
3292 inlined function. */
3293 if (cond
>= predicate_first_dynamic_condition
)
3295 struct condition
*c
;
3297 c
= &(*callee_info
->conds
)[cond
3299 predicate_first_dynamic_condition
];
3300 /* See if we can remap condition operand to caller's operand.
3301 Otherwise give up. */
3302 if (!operand_map
.exists ()
3303 || (int) operand_map
.length () <= c
->operand_num
3304 || operand_map
[c
->operand_num
] == -1
3305 /* TODO: For non-aggregate conditions, adding an offset is
3306 basically an arithmetic jump function processing which
3307 we should support in future. */
3308 || ((!c
->agg_contents
|| !c
->by_ref
)
3309 && offset_map
[c
->operand_num
] > 0)
3310 || (c
->agg_contents
&& c
->by_ref
3311 && offset_map
[c
->operand_num
] < 0))
3312 cond_predicate
= true_predicate ();
3315 struct agg_position_info ap
;
3316 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3317 if (offset_delta
< 0)
3319 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3322 gcc_assert (!c
->agg_contents
3323 || c
->by_ref
|| offset_delta
== 0);
3324 ap
.offset
= c
->offset
+ offset_delta
;
3325 ap
.agg_contents
= c
->agg_contents
;
3326 ap
.by_ref
= c
->by_ref
;
3327 cond_predicate
= add_condition (info
,
3328 operand_map
[c
->operand_num
],
3329 &ap
, c
->code
, c
->val
);
3332 /* Fixed conditions remains same, construct single
3333 condition predicate. */
3336 cond_predicate
.clause
[0] = 1 << cond
;
3337 cond_predicate
.clause
[1] = 0;
3339 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3342 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3344 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3348 /* Update summary information of inline clones after inlining.
3349 Compute peak stack usage. */
3352 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3354 struct cgraph_edge
*e
;
3355 struct inline_summary
*callee_info
= inline_summary (node
);
3356 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
3359 callee_info
->stack_frame_offset
3360 = caller_info
->stack_frame_offset
3361 + caller_info
->estimated_self_stack_size
;
3362 peak
= callee_info
->stack_frame_offset
3363 + callee_info
->estimated_self_stack_size
;
3364 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3365 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3366 ipa_propagate_frequency (node
);
3367 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3369 if (!e
->inline_failed
)
3370 inline_update_callee_summaries (e
->callee
, depth
);
3371 inline_edge_summary (e
)->loop_depth
+= depth
;
3373 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3374 inline_edge_summary (e
)->loop_depth
+= depth
;
3377 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3378 When functoin A is inlined in B and A calls C with parameter that
3379 changes with probability PROB1 and C is known to be passthroug
3380 of argument if B that change with probability PROB2, the probability
3381 of change is now PROB1*PROB2. */
3384 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3385 struct cgraph_edge
*edge
)
3387 if (ipa_node_params_vector
.exists ())
3390 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3391 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3392 struct inline_edge_summary
*inlined_es
3393 = inline_edge_summary (inlined_edge
);
3395 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3397 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3398 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3399 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3400 < (int) inlined_es
->param
.length ()))
3402 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3403 int prob1
= es
->param
[i
].change_prob
;
3404 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3405 int prob
= combine_probabilities (prob1
, prob2
);
3407 if (prob1
&& prob2
&& !prob
)
3410 es
->param
[i
].change_prob
= prob
;
3416 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3418 Remap predicates of callees of NODE. Rest of arguments match
3421 Also update change probabilities. */
3424 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3425 struct cgraph_node
*node
,
3426 struct inline_summary
*info
,
3427 struct inline_summary
*callee_info
,
3428 vec
<int> operand_map
,
3429 vec
<int> offset_map
,
3430 clause_t possible_truths
,
3431 struct predicate
*toplev_predicate
)
3433 struct cgraph_edge
*e
;
3434 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3436 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3439 if (e
->inline_failed
)
3441 remap_edge_change_prob (inlined_edge
, e
);
3445 p
= remap_predicate (info
, callee_info
,
3446 es
->predicate
, operand_map
, offset_map
,
3447 possible_truths
, toplev_predicate
);
3448 edge_set_predicate (e
, &p
);
3449 /* TODO: We should remove the edge for code that will be
3450 optimized out, but we need to keep verifiers and tree-inline
3451 happy. Make it cold for now. */
3452 if (false_predicate_p (&p
))
3459 edge_set_predicate (e
, toplev_predicate
);
3462 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3463 operand_map
, offset_map
, possible_truths
,
3466 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3468 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3471 remap_edge_change_prob (inlined_edge
, e
);
3474 p
= remap_predicate (info
, callee_info
,
3475 es
->predicate
, operand_map
, offset_map
,
3476 possible_truths
, toplev_predicate
);
3477 edge_set_predicate (e
, &p
);
3478 /* TODO: We should remove the edge for code that will be optimized
3479 out, but we need to keep verifiers and tree-inline happy.
3480 Make it cold for now. */
3481 if (false_predicate_p (&p
))
3488 edge_set_predicate (e
, toplev_predicate
);
3492 /* Same as remap_predicate, but set result into hint *HINT. */
3495 remap_hint_predicate (struct inline_summary
*info
,
3496 struct inline_summary
*callee_info
,
3497 struct predicate
**hint
,
3498 vec
<int> operand_map
,
3499 vec
<int> offset_map
,
3500 clause_t possible_truths
,
3501 struct predicate
*toplev_predicate
)
3507 p
= remap_predicate (info
, callee_info
,
3509 operand_map
, offset_map
,
3510 possible_truths
, toplev_predicate
);
3511 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3514 set_hint_predicate (hint
, p
);
3516 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3520 /* We inlined EDGE. Update summary of the function we inlined into. */
3523 inline_merge_summary (struct cgraph_edge
*edge
)
3525 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
3526 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3527 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3528 struct inline_summary
*info
= inline_summary (to
);
3529 clause_t clause
= 0; /* not_inline is known to be false. */
3531 vec
<int> operand_map
= vNULL
;
3532 vec
<int> offset_map
= vNULL
;
3534 struct predicate toplev_predicate
;
3535 struct predicate true_p
= true_predicate ();
3536 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3539 toplev_predicate
= *es
->predicate
;
3541 toplev_predicate
= true_predicate ();
3543 if (ipa_node_params_vector
.exists () && callee_info
->conds
)
3545 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3546 int count
= ipa_get_cs_argument_count (args
);
3549 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3552 operand_map
.safe_grow_cleared (count
);
3553 offset_map
.safe_grow_cleared (count
);
3555 for (i
= 0; i
< count
; i
++)
3557 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3560 /* TODO: handle non-NOPs when merging. */
3561 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3563 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3564 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3565 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3568 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3570 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3571 if (offset
>= 0 && offset
< INT_MAX
)
3573 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3574 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3576 offset_map
[i
] = offset
;
3579 operand_map
[i
] = map
;
3580 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3583 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3585 struct predicate p
= remap_predicate (info
, callee_info
,
3586 &e
->predicate
, operand_map
,
3589 if (!false_predicate_p (&p
))
3591 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3592 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3593 int prob
= predicate_probability (callee_info
->conds
,
3596 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3597 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3598 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3599 if (prob
!= REG_BR_PROB_BASE
3600 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3602 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3603 (double) prob
/ REG_BR_PROB_BASE
);
3605 account_size_time (info
, e
->size
, add_time
, &p
);
3608 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3609 offset_map
, clause
, &toplev_predicate
);
3610 remap_hint_predicate (info
, callee_info
,
3611 &callee_info
->loop_iterations
,
3612 operand_map
, offset_map
, clause
, &toplev_predicate
);
3613 remap_hint_predicate (info
, callee_info
,
3614 &callee_info
->loop_stride
,
3615 operand_map
, offset_map
, clause
, &toplev_predicate
);
3616 remap_hint_predicate (info
, callee_info
,
3617 &callee_info
->array_index
,
3618 operand_map
, offset_map
, clause
, &toplev_predicate
);
3620 inline_update_callee_summaries (edge
->callee
,
3621 inline_edge_summary (edge
)->loop_depth
);
3623 /* We do not maintain predicates of inlined edges, free it. */
3624 edge_set_predicate (edge
, &true_p
);
3625 /* Similarly remove param summaries. */
3626 es
->param
.release ();
3627 operand_map
.release ();
3628 offset_map
.release ();
3631 /* For performance reasons inline_merge_summary is not updating overall size
3632 and time. Recompute it. */
3635 inline_update_overall_summary (struct cgraph_node
*node
)
3637 struct inline_summary
*info
= inline_summary (node
);
3643 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3645 info
->size
+= e
->size
, info
->time
+= e
->time
;
3646 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3647 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3649 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3651 ~(clause_t
) (1 << predicate_false_condition
),
3652 vNULL
, vNULL
, vNULL
);
3653 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3654 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3657 /* Return hints derrived from EDGE. */
3659 simple_edge_hints (struct cgraph_edge
*edge
)
3662 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3663 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3664 if (inline_summary (to
)->scc_no
3665 && inline_summary (to
)->scc_no
== inline_summary (edge
->callee
)->scc_no
3666 && !edge
->recursive_p ())
3667 hints
|= INLINE_HINT_same_scc
;
3669 if (to
->lto_file_data
&& edge
->callee
->lto_file_data
3670 && to
->lto_file_data
!= edge
->callee
->lto_file_data
)
3671 hints
|= INLINE_HINT_cross_module
;
3676 /* Estimate the time cost for the caller when inlining EDGE.
3677 Only to be called via estimate_edge_time, that handles the
3680 When caching, also update the cache entry. Compute both time and
3681 size, since we always need both metrics eventually. */
3684 do_estimate_edge_time (struct cgraph_edge
*edge
)
3689 struct cgraph_node
*callee
;
3691 vec
<tree
> known_vals
;
3692 vec
<ipa_polymorphic_call_context
> known_contexts
;
3693 vec
<ipa_agg_jump_function_p
> known_aggs
;
3694 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3697 callee
= edge
->callee
->ultimate_alias_target ();
3699 gcc_checking_assert (edge
->inline_failed
);
3700 evaluate_properties_for_edge (edge
, true,
3701 &clause
, &known_vals
, &known_contexts
,
3703 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3704 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3706 /* When we have profile feedback, we can quite safely identify hot
3707 edges and for those we disable size limits. Don't do that when
3708 probability that caller will call the callee is low however, since it
3709 may hurt optimization of the caller's hot path. */
3710 if (edge
->count
&& edge
->maybe_hot_p ()
3712 > (edge
->caller
->global
.inlined_to
3713 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3714 hints
|= INLINE_HINT_known_hot
;
3716 known_vals
.release ();
3717 known_contexts
.release ();
3718 known_aggs
.release ();
3719 gcc_checking_assert (size
>= 0);
3720 gcc_checking_assert (time
>= 0);
3722 /* When caching, update the cache entry. */
3723 if (edge_growth_cache
.exists ())
3725 inline_summary (edge
->callee
)->min_size
= min_size
;
3726 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3727 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3728 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3730 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3731 hints
|= simple_edge_hints (edge
);
3732 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3738 /* Return estimated callee growth after inlining EDGE.
3739 Only to be called via estimate_edge_size. */
3742 do_estimate_edge_size (struct cgraph_edge
*edge
)
3745 struct cgraph_node
*callee
;
3747 vec
<tree
> known_vals
;
3748 vec
<ipa_polymorphic_call_context
> known_contexts
;
3749 vec
<ipa_agg_jump_function_p
> known_aggs
;
3751 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3753 if (edge_growth_cache
.exists ())
3755 do_estimate_edge_time (edge
);
3756 size
= edge_growth_cache
[edge
->uid
].size
;
3757 gcc_checking_assert (size
);
3758 return size
- (size
> 0);
3761 callee
= edge
->callee
->ultimate_alias_target ();
3763 /* Early inliner runs without caching, go ahead and do the dirty work. */
3764 gcc_checking_assert (edge
->inline_failed
);
3765 evaluate_properties_for_edge (edge
, true,
3766 &clause
, &known_vals
, &known_contexts
,
3768 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3769 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3770 known_vals
.release ();
3771 known_contexts
.release ();
3772 known_aggs
.release ();
3777 /* Estimate the growth of the caller when inlining EDGE.
3778 Only to be called via estimate_edge_size. */
3781 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3784 struct cgraph_node
*callee
;
3786 vec
<tree
> known_vals
;
3787 vec
<ipa_polymorphic_call_context
> known_contexts
;
3788 vec
<ipa_agg_jump_function_p
> known_aggs
;
3790 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3792 if (edge_growth_cache
.exists ())
3794 do_estimate_edge_time (edge
);
3795 hints
= edge_growth_cache
[edge
->uid
].hints
;
3796 gcc_checking_assert (hints
);
3800 callee
= edge
->callee
->ultimate_alias_target ();
3802 /* Early inliner runs without caching, go ahead and do the dirty work. */
3803 gcc_checking_assert (edge
->inline_failed
);
3804 evaluate_properties_for_edge (edge
, true,
3805 &clause
, &known_vals
, &known_contexts
,
3807 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3808 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3809 known_vals
.release ();
3810 known_contexts
.release ();
3811 known_aggs
.release ();
3812 hints
|= simple_edge_hints (edge
);
3817 /* Estimate self time of the function NODE after inlining EDGE. */
3820 estimate_time_after_inlining (struct cgraph_node
*node
,
3821 struct cgraph_edge
*edge
)
3823 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3824 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3827 inline_summary (node
)->time
+ estimate_edge_time (edge
);
3830 if (time
> MAX_TIME
)
3834 return inline_summary (node
)->time
;
3838 /* Estimate the size of NODE after inlining EDGE which should be an
3839 edge to either NODE or a call inlined into NODE. */
3842 estimate_size_after_inlining (struct cgraph_node
*node
,
3843 struct cgraph_edge
*edge
)
3845 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3846 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3848 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
3849 gcc_assert (size
>= 0);
3852 return inline_summary (node
)->size
;
3858 struct cgraph_node
*node
;
3859 bool self_recursive
;
3864 /* Worker for do_estimate_growth. Collect growth for all callers. */
3867 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3869 struct cgraph_edge
*e
;
3870 struct growth_data
*d
= (struct growth_data
*) data
;
3872 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3874 gcc_checking_assert (e
->inline_failed
);
3876 if (e
->caller
== d
->node
3877 || (e
->caller
->global
.inlined_to
3878 && e
->caller
->global
.inlined_to
== d
->node
))
3879 d
->self_recursive
= true;
3880 d
->growth
+= estimate_edge_growth (e
);
3886 /* Estimate the growth caused by inlining NODE into all callees. */
3889 do_estimate_growth (struct cgraph_node
*node
)
3891 struct growth_data d
= { node
, 0, false };
3892 struct inline_summary
*info
= inline_summary (node
);
3894 node
->call_for_symbol_thunks_and_aliases (do_estimate_growth_1
, &d
, true);
3896 /* For self recursive functions the growth estimation really should be
3897 infinity. We don't want to return very large values because the growth
3898 plays various roles in badness computation fractions. Be sure to not
3899 return zero or negative growths. */
3900 if (d
.self_recursive
)
3901 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3902 else if (DECL_EXTERNAL (node
->decl
))
3906 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3907 d
.growth
-= info
->size
;
3908 /* COMDAT functions are very often not shared across multiple units
3909 since they come from various template instantiations.
3910 Take this into account. */
3911 else if (DECL_COMDAT (node
->decl
)
3912 && node
->can_remove_if_no_direct_calls_p ())
3913 d
.growth
-= (info
->size
3914 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3918 if (node_growth_cache
.exists ())
3920 if ((int) node_growth_cache
.length () <= node
->uid
)
3921 node_growth_cache
.safe_grow_cleared (symtab
->cgraph_max_uid
);
3922 node_growth_cache
[node
->uid
] = d
.growth
+ (d
.growth
>= 0);
3928 /* Make cheap estimation if growth of NODE is likely positive knowing
3929 EDGE_GROWTH of one particular edge.
3930 We assume that most of other edges will have similar growth
3931 and skip computation if there are too many callers. */
3934 growth_likely_positive (struct cgraph_node
*node
, int edge_growth ATTRIBUTE_UNUSED
)
3938 struct cgraph_edge
*e
;
3939 gcc_checking_assert (edge_growth
> 0);
3941 /* Unlike for functions called once, we play unsafe with
3942 COMDATs. We can allow that since we know functions
3943 in consideration are small (and thus risk is small) and
3944 moreover grow estimates already accounts that COMDAT
3945 functions may or may not disappear when eliminated from
3946 current unit. With good probability making aggressive
3947 choice in all units is going to make overall program
3950 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
3952 cgraph_will_be_removed_from_program_if_no_direct_calls */
3953 if (DECL_EXTERNAL (node
->decl
)
3954 || !node
->can_remove_if_no_direct_calls_p ())
3957 /* If there is cached value, just go ahead. */
3958 if ((int)node_growth_cache
.length () > node
->uid
3959 && (ret
= node_growth_cache
[node
->uid
]))
3961 if (!node
->will_be_removed_from_program_if_no_direct_calls_p ()
3962 && (!DECL_COMDAT (node
->decl
)
3963 || !node
->can_remove_if_no_direct_calls_p ()))
3965 max_callers
= inline_summary (node
)->size
* 4 / edge_growth
+ 2;
3967 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3973 return estimate_growth (node
) > 0;
3977 /* This function performs intraprocedural analysis in NODE that is required to
3978 inline indirect calls. */
3981 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
3983 ipa_analyze_node (node
);
3984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3986 ipa_print_node_params (dump_file
, node
);
3987 ipa_print_node_jump_functions (dump_file
, node
);
3992 /* Note function body size. */
3995 inline_analyze_function (struct cgraph_node
*node
)
3997 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4000 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4001 node
->name (), node
->order
);
4002 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4003 inline_indirect_intraprocedural_analysis (node
);
4004 compute_inline_parameters (node
, false);
4007 struct cgraph_edge
*e
;
4008 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4010 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4011 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4012 e
->call_stmt_cannot_inline_p
= true;
4014 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4016 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4017 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4018 e
->call_stmt_cannot_inline_p
= true;
4026 /* Called when new function is inserted to callgraph late. */
4029 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
4031 inline_analyze_function (node
);
4035 /* Note function body size. */
4038 inline_generate_summary (void)
4040 struct cgraph_node
*node
;
4042 /* When not optimizing, do not bother to analyze. Inlining is still done
4043 because edge redirection needs to happen there. */
4044 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4047 function_insertion_hook_holder
=
4048 symtab
->add_cgraph_insertion_hook (&add_new_function
, NULL
);
4050 ipa_register_cgraph_hooks ();
4051 inline_free_summary ();
4053 FOR_EACH_DEFINED_FUNCTION (node
)
4055 inline_analyze_function (node
);
4059 /* Read predicate from IB. */
4061 static struct predicate
4062 read_predicate (struct lto_input_block
*ib
)
4064 struct predicate out
;
4070 gcc_assert (k
<= MAX_CLAUSES
);
4071 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4075 /* Zero-initialize the remaining clauses in OUT. */
4076 while (k
<= MAX_CLAUSES
)
4077 out
.clause
[k
++] = 0;
4083 /* Write inline summary for edge E to OB. */
4086 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4088 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4092 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4093 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4094 es
->loop_depth
= streamer_read_uhwi (ib
);
4095 p
= read_predicate (ib
);
4096 edge_set_predicate (e
, &p
);
4097 length
= streamer_read_uhwi (ib
);
4100 es
->param
.safe_grow_cleared (length
);
4101 for (i
= 0; i
< length
; i
++)
4102 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4107 /* Stream in inline summaries from the section. */
4110 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4113 const struct lto_function_header
*header
=
4114 (const struct lto_function_header
*) data
;
4115 const int cfg_offset
= sizeof (struct lto_function_header
);
4116 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4117 const int string_offset
= main_offset
+ header
->main_size
;
4118 struct data_in
*data_in
;
4119 unsigned int i
, count2
, j
;
4120 unsigned int f_count
;
4122 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
);
4125 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4126 header
->string_size
, vNULL
);
4127 f_count
= streamer_read_uhwi (&ib
);
4128 for (i
= 0; i
< f_count
; i
++)
4131 struct cgraph_node
*node
;
4132 struct inline_summary
*info
;
4133 lto_symtab_encoder_t encoder
;
4134 struct bitpack_d bp
;
4135 struct cgraph_edge
*e
;
4138 index
= streamer_read_uhwi (&ib
);
4139 encoder
= file_data
->symtab_node_encoder
;
4140 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4142 info
= inline_summary (node
);
4144 info
->estimated_stack_size
4145 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4146 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4147 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4149 bp
= streamer_read_bitpack (&ib
);
4150 info
->inlinable
= bp_unpack_value (&bp
, 1);
4152 count2
= streamer_read_uhwi (&ib
);
4153 gcc_assert (!info
->conds
);
4154 for (j
= 0; j
< count2
; j
++)
4157 c
.operand_num
= streamer_read_uhwi (&ib
);
4158 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4159 c
.val
= stream_read_tree (&ib
, data_in
);
4160 bp
= streamer_read_bitpack (&ib
);
4161 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4162 c
.by_ref
= bp_unpack_value (&bp
, 1);
4164 c
.offset
= streamer_read_uhwi (&ib
);
4165 vec_safe_push (info
->conds
, c
);
4167 count2
= streamer_read_uhwi (&ib
);
4168 gcc_assert (!info
->entry
);
4169 for (j
= 0; j
< count2
; j
++)
4171 struct size_time_entry e
;
4173 e
.size
= streamer_read_uhwi (&ib
);
4174 e
.time
= streamer_read_uhwi (&ib
);
4175 e
.predicate
= read_predicate (&ib
);
4177 vec_safe_push (info
->entry
, e
);
4180 p
= read_predicate (&ib
);
4181 set_hint_predicate (&info
->loop_iterations
, p
);
4182 p
= read_predicate (&ib
);
4183 set_hint_predicate (&info
->loop_stride
, p
);
4184 p
= read_predicate (&ib
);
4185 set_hint_predicate (&info
->array_index
, p
);
4186 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4187 read_inline_edge_summary (&ib
, e
);
4188 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4189 read_inline_edge_summary (&ib
, e
);
4192 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4194 lto_data_in_delete (data_in
);
4198 /* Read inline summary. Jump functions are shared among ipa-cp
4199 and inliner, so when ipa-cp is active, we don't need to write them
4203 inline_read_summary (void)
4205 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4206 struct lto_file_decl_data
*file_data
;
4209 inline_summary_alloc ();
4211 while ((file_data
= file_data_vec
[j
++]))
4214 const char *data
= lto_get_section_data (file_data
,
4215 LTO_section_inline_summary
,
4218 inline_read_section (file_data
, data
, len
);
4220 /* Fatal error here. We do not want to support compiling ltrans units
4221 with different version of compiler or different flags than the WPA
4222 unit, so this should never happen. */
4223 fatal_error ("ipa inline summary is missing in input file");
4227 ipa_register_cgraph_hooks ();
4229 ipa_prop_read_jump_functions ();
4231 function_insertion_hook_holder
=
4232 symtab
->add_cgraph_insertion_hook (&add_new_function
, NULL
);
4236 /* Write predicate P to OB. */
4239 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4243 for (j
= 0; p
->clause
[j
]; j
++)
4245 gcc_assert (j
< MAX_CLAUSES
);
4246 streamer_write_uhwi (ob
, p
->clause
[j
]);
4248 streamer_write_uhwi (ob
, 0);
4252 /* Write inline summary for edge E to OB. */
4255 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4257 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4260 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4261 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4262 streamer_write_uhwi (ob
, es
->loop_depth
);
4263 write_predicate (ob
, es
->predicate
);
4264 streamer_write_uhwi (ob
, es
->param
.length ());
4265 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4266 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4270 /* Write inline summary for node in SET.
4271 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4272 active, we don't need to write them twice. */
4275 inline_write_summary (void)
4277 struct cgraph_node
*node
;
4278 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4279 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4280 unsigned int count
= 0;
4283 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4285 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4286 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4287 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4290 streamer_write_uhwi (ob
, count
);
4292 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4294 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4295 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4296 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4298 struct inline_summary
*info
= inline_summary (node
);
4299 struct bitpack_d bp
;
4300 struct cgraph_edge
*edge
;
4303 struct condition
*c
;
4305 streamer_write_uhwi (ob
,
4306 lto_symtab_encoder_encode (encoder
,
4309 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4310 streamer_write_hwi (ob
, info
->self_size
);
4311 streamer_write_hwi (ob
, info
->self_time
);
4312 bp
= bitpack_create (ob
->main_stream
);
4313 bp_pack_value (&bp
, info
->inlinable
, 1);
4314 streamer_write_bitpack (&bp
);
4315 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4316 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4318 streamer_write_uhwi (ob
, c
->operand_num
);
4319 streamer_write_uhwi (ob
, c
->code
);
4320 stream_write_tree (ob
, c
->val
, true);
4321 bp
= bitpack_create (ob
->main_stream
);
4322 bp_pack_value (&bp
, c
->agg_contents
, 1);
4323 bp_pack_value (&bp
, c
->by_ref
, 1);
4324 streamer_write_bitpack (&bp
);
4325 if (c
->agg_contents
)
4326 streamer_write_uhwi (ob
, c
->offset
);
4328 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4329 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4331 streamer_write_uhwi (ob
, e
->size
);
4332 streamer_write_uhwi (ob
, e
->time
);
4333 write_predicate (ob
, &e
->predicate
);
4335 write_predicate (ob
, info
->loop_iterations
);
4336 write_predicate (ob
, info
->loop_stride
);
4337 write_predicate (ob
, info
->array_index
);
4338 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4339 write_inline_edge_summary (ob
, edge
);
4340 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4341 write_inline_edge_summary (ob
, edge
);
4344 streamer_write_char_stream (ob
->main_stream
, 0);
4345 produce_asm (ob
, NULL
);
4346 destroy_output_block (ob
);
4348 if (optimize
&& !flag_ipa_cp
)
4349 ipa_prop_write_jump_functions ();
4353 /* Release inline summary. */
4356 inline_free_summary (void)
4358 struct cgraph_node
*node
;
4359 if (function_insertion_hook_holder
)
4360 symtab
->remove_cgraph_insertion_hook (function_insertion_hook_holder
);
4361 function_insertion_hook_holder
= NULL
;
4362 if (node_removal_hook_holder
)
4363 symtab
->remove_cgraph_removal_hook (node_removal_hook_holder
);
4364 node_removal_hook_holder
= NULL
;
4365 if (edge_removal_hook_holder
)
4366 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4367 edge_removal_hook_holder
= NULL
;
4368 if (node_duplication_hook_holder
)
4369 symtab
->remove_cgraph_duplication_hook (node_duplication_hook_holder
);
4370 node_duplication_hook_holder
= NULL
;
4371 if (edge_duplication_hook_holder
)
4372 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4373 edge_duplication_hook_holder
= NULL
;
4374 if (!inline_edge_summary_vec
.exists ())
4376 FOR_EACH_DEFINED_FUNCTION (node
)
4378 reset_inline_summary (node
);
4379 vec_free (inline_summary_vec
);
4380 inline_edge_summary_vec
.release ();
4381 if (edge_predicate_pool
)
4382 free_alloc_pool (edge_predicate_pool
);
4383 edge_predicate_pool
= 0;