1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2015 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Analysis used by the inliner and other passes limiting code size growth.
23 We estimate for each function
25 - average function execution time
26 - inlining size benefit (that is how much of function body size
27 and its call sequence is expected to disappear by inlining)
28 - inlining time benefit
31 - call statement size and time
33 inlinie_summary datastructures store above information locally (i.e.
34 parameters of the function itself) and globally (i.e. parameters of
35 the function created by applying all the inline decisions already
36 present in the callgraph).
38 We provide accestor to the inline_summary datastructure and
39 basic logic updating the parameters when inlining is performed.
41 The summaries are context sensitive. Context means
42 1) partial assignment of known constant values of operands
43 2) whether function is inlined into the call or not.
44 It is easy to add more variants. To represent function size and time
45 that depends on context (i.e. it is known to be optimized away when
46 context is known either by inlining or from IP-CP and clonning),
47 we use predicates. Predicates are logical formulas in
48 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
49 specifying what conditions must be true. Conditions are simple test
50 of the form described above.
52 In order to make predicate (possibly) true, all of its clauses must
53 be (possibly) true. To make clause (possibly) true, one of conditions
54 it mentions must be (possibly) true. There are fixed bounds on
55 number of clauses and conditions and all the manipulation functions
56 are conservative in positive direction. I.e. we may lose precision
57 by thinking that predicate may be true even when it is not.
59 estimate_edge_size and estimate_edge_growth can be used to query
60 function size/time in the given context. inline_merge_summary merges
61 properties of caller and callee after inlining.
63 Finally pass_inline_parameters is exported. This is used to drive
64 computation of function parameters used by the early inliner. IPA
65 inlined performs analysis via its analyze_function method. */
69 #include "coretypes.h"
75 #include "fold-const.h"
76 #include "stor-layout.h"
77 #include "stringpool.h"
78 #include "print-tree.h"
79 #include "tree-inline.h"
80 #include "langhooks.h"
82 #include "diagnostic.h"
83 #include "gimple-pretty-print.h"
85 #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 "plugin-api.h"
111 #include "alloc-pool.h"
112 #include "symbol-summary.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_2edge_hook_list
*edge_duplication_hook_holder
;
151 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
152 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
153 static void inline_edge_duplication_hook (struct cgraph_edge
*,
154 struct cgraph_edge
*, void *);
156 /* VECtor holding inline summaries.
157 In GGC memory because conditions might point to constant trees. */
158 function_summary
<inline_summary
*> *inline_summaries
;
159 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
161 /* Cached node/edge growths. */
162 vec
<edge_growth_cache_entry
> edge_growth_cache
;
164 /* Edge predicates goes here. */
165 static pool_allocator
<predicate
> edge_predicate_pool ("edge predicates", 10);
167 /* Return true predicate (tautology).
168 We represent it by empty list of clauses. */
170 static inline struct predicate
171 true_predicate (void)
179 /* Return predicate testing single condition number COND. */
181 static inline struct predicate
182 single_cond_predicate (int cond
)
185 p
.clause
[0] = 1 << cond
;
191 /* Return false predicate. First clause require false condition. */
193 static inline struct predicate
194 false_predicate (void)
196 return single_cond_predicate (predicate_false_condition
);
200 /* Return true if P is (true). */
203 true_predicate_p (struct predicate
*p
)
205 return !p
->clause
[0];
209 /* Return true if P is (false). */
212 false_predicate_p (struct predicate
*p
)
214 if (p
->clause
[0] == (1 << predicate_false_condition
))
216 gcc_checking_assert (!p
->clause
[1]
217 && p
->clause
[0] == 1 << predicate_false_condition
);
224 /* Return predicate that is set true when function is not inlined. */
226 static inline struct predicate
227 not_inlined_predicate (void)
229 return single_cond_predicate (predicate_not_inlined_condition
);
232 /* Simple description of whether a memory load or a condition refers to a load
233 from an aggregate and if so, how and where from in the aggregate.
234 Individual fields have the same meaning like fields with the same name in
237 struct agg_position_info
239 HOST_WIDE_INT offset
;
244 /* Add condition to condition list CONDS. AGGPOS describes whether the used
245 oprand is loaded from an aggregate and where in the aggregate it is. It can
246 be NULL, which means this not a load from an aggregate. */
248 static struct predicate
249 add_condition (struct inline_summary
*summary
, int operand_num
,
250 struct agg_position_info
*aggpos
,
251 enum tree_code code
, tree val
)
255 struct condition new_cond
;
256 HOST_WIDE_INT offset
;
257 bool agg_contents
, by_ref
;
261 offset
= aggpos
->offset
;
262 agg_contents
= aggpos
->agg_contents
;
263 by_ref
= aggpos
->by_ref
;
268 agg_contents
= false;
272 gcc_checking_assert (operand_num
>= 0);
273 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
275 if (c
->operand_num
== operand_num
278 && c
->agg_contents
== agg_contents
279 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
280 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
282 /* Too many conditions. Give up and return constant true. */
283 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
284 return true_predicate ();
286 new_cond
.operand_num
= operand_num
;
287 new_cond
.code
= code
;
289 new_cond
.agg_contents
= agg_contents
;
290 new_cond
.by_ref
= by_ref
;
291 new_cond
.offset
= offset
;
292 vec_safe_push (summary
->conds
, new_cond
);
293 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
297 /* Add clause CLAUSE into the predicate P. */
300 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
304 int insert_here
= -1;
311 /* False clause makes the whole predicate false. Kill the other variants. */
312 if (clause
== (1 << predicate_false_condition
))
314 p
->clause
[0] = (1 << predicate_false_condition
);
318 if (false_predicate_p (p
))
321 /* No one should be silly enough to add false into nontrivial clauses. */
322 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
324 /* Look where to insert the clause. At the same time prune out
325 clauses of P that are implied by the new clause and thus
327 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
329 p
->clause
[i2
] = p
->clause
[i
];
334 /* If p->clause[i] implies clause, there is nothing to add. */
335 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
337 /* We had nothing to add, none of clauses should've become
339 gcc_checking_assert (i
== i2
);
343 if (p
->clause
[i
] < clause
&& insert_here
< 0)
346 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
347 Otherwise the p->clause[i] has to stay. */
348 if ((p
->clause
[i
] & clause
) != clause
)
352 /* Look for clauses that are obviously true. I.e.
353 op0 == 5 || op0 != 5. */
354 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
357 if (!(clause
& (1 << c1
)))
359 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
360 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
361 and thus there is no point for looking for them. */
362 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
364 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
365 if (clause
& (1 << c2
))
368 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
370 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
371 if (cc1
->operand_num
== cc2
->operand_num
372 && cc1
->val
== cc2
->val
373 && cc2
->code
!= IS_NOT_CONSTANT
374 && cc2
->code
!= CHANGED
375 && cc1
->code
== invert_tree_comparison (cc2
->code
,
376 HONOR_NANS (cc1
->val
)))
382 /* We run out of variants. Be conservative in positive direction. */
383 if (i2
== MAX_CLAUSES
)
385 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
386 p
->clause
[i2
+ 1] = 0;
387 if (insert_here
>= 0)
388 for (; i2
> insert_here
; i2
--)
389 p
->clause
[i2
] = p
->clause
[i2
- 1];
392 p
->clause
[insert_here
] = clause
;
398 static struct predicate
399 and_predicates (conditions conditions
,
400 struct predicate
*p
, struct predicate
*p2
)
402 struct predicate out
= *p
;
405 /* Avoid busy work. */
406 if (false_predicate_p (p2
) || true_predicate_p (p
))
408 if (false_predicate_p (p
) || true_predicate_p (p2
))
411 /* See how far predicates match. */
412 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
414 gcc_checking_assert (i
< MAX_CLAUSES
);
417 /* Combine the predicates rest. */
418 for (; p2
->clause
[i
]; i
++)
420 gcc_checking_assert (i
< MAX_CLAUSES
);
421 add_clause (conditions
, &out
, p2
->clause
[i
]);
427 /* Return true if predicates are obviously equal. */
430 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
433 for (i
= 0; p
->clause
[i
]; i
++)
435 gcc_checking_assert (i
< MAX_CLAUSES
);
436 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
437 gcc_checking_assert (!p2
->clause
[i
]
438 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
439 if (p
->clause
[i
] != p2
->clause
[i
])
442 return !p2
->clause
[i
];
448 static struct predicate
449 or_predicates (conditions conditions
,
450 struct predicate
*p
, struct predicate
*p2
)
452 struct predicate out
= true_predicate ();
455 /* Avoid busy work. */
456 if (false_predicate_p (p2
) || true_predicate_p (p
))
458 if (false_predicate_p (p
) || true_predicate_p (p2
))
460 if (predicates_equal_p (p
, p2
))
463 /* OK, combine the predicates. */
464 for (i
= 0; p
->clause
[i
]; i
++)
465 for (j
= 0; p2
->clause
[j
]; j
++)
467 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
468 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
474 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
475 if predicate P is known to be false. */
478 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
482 /* True remains true. */
483 if (true_predicate_p (p
))
486 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
488 /* See if we can find clause we can disprove. */
489 for (i
= 0; p
->clause
[i
]; i
++)
491 gcc_checking_assert (i
< MAX_CLAUSES
);
492 if (!(p
->clause
[i
] & possible_truths
))
498 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
499 instruction will be recomputed per invocation of the inlined call. */
502 predicate_probability (conditions conds
,
503 struct predicate
*p
, clause_t possible_truths
,
504 vec
<inline_param_summary
> inline_param_summary
)
507 int combined_prob
= REG_BR_PROB_BASE
;
509 /* True remains true. */
510 if (true_predicate_p (p
))
511 return REG_BR_PROB_BASE
;
513 if (false_predicate_p (p
))
516 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
518 /* See if we can find clause we can disprove. */
519 for (i
= 0; p
->clause
[i
]; i
++)
521 gcc_checking_assert (i
< MAX_CLAUSES
);
522 if (!(p
->clause
[i
] & possible_truths
))
528 if (!inline_param_summary
.exists ())
529 return REG_BR_PROB_BASE
;
530 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
531 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
533 if (i2
>= predicate_first_dynamic_condition
)
536 &(*conds
)[i2
- predicate_first_dynamic_condition
];
537 if (c
->code
== CHANGED
539 (int) inline_param_summary
.length ()))
542 inline_param_summary
[c
->operand_num
].change_prob
;
543 this_prob
= MAX (this_prob
, iprob
);
546 this_prob
= REG_BR_PROB_BASE
;
549 this_prob
= REG_BR_PROB_BASE
;
551 combined_prob
= MIN (this_prob
, combined_prob
);
556 return combined_prob
;
560 /* Dump conditional COND. */
563 dump_condition (FILE *f
, conditions conditions
, int cond
)
566 if (cond
== predicate_false_condition
)
567 fprintf (f
, "false");
568 else if (cond
== predicate_not_inlined_condition
)
569 fprintf (f
, "not inlined");
572 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
573 fprintf (f
, "op%i", c
->operand_num
);
575 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
576 c
->by_ref
? "ref " : "", c
->offset
);
577 if (c
->code
== IS_NOT_CONSTANT
)
579 fprintf (f
, " not constant");
582 if (c
->code
== CHANGED
)
584 fprintf (f
, " changed");
587 fprintf (f
, " %s ", op_symbol_code (c
->code
));
588 print_generic_expr (f
, c
->val
, 1);
593 /* Dump clause CLAUSE. */
596 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
603 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
604 if (clause
& (1 << i
))
609 dump_condition (f
, conds
, i
);
615 /* Dump predicate PREDICATE. */
618 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
621 if (true_predicate_p (pred
))
622 dump_clause (f
, conds
, 0);
624 for (i
= 0; pred
->clause
[i
]; i
++)
628 dump_clause (f
, conds
, pred
->clause
[i
]);
634 /* Dump inline hints. */
636 dump_inline_hints (FILE *f
, inline_hints hints
)
640 fprintf (f
, "inline hints:");
641 if (hints
& INLINE_HINT_indirect_call
)
643 hints
&= ~INLINE_HINT_indirect_call
;
644 fprintf (f
, " indirect_call");
646 if (hints
& INLINE_HINT_loop_iterations
)
648 hints
&= ~INLINE_HINT_loop_iterations
;
649 fprintf (f
, " loop_iterations");
651 if (hints
& INLINE_HINT_loop_stride
)
653 hints
&= ~INLINE_HINT_loop_stride
;
654 fprintf (f
, " loop_stride");
656 if (hints
& INLINE_HINT_same_scc
)
658 hints
&= ~INLINE_HINT_same_scc
;
659 fprintf (f
, " same_scc");
661 if (hints
& INLINE_HINT_in_scc
)
663 hints
&= ~INLINE_HINT_in_scc
;
664 fprintf (f
, " in_scc");
666 if (hints
& INLINE_HINT_cross_module
)
668 hints
&= ~INLINE_HINT_cross_module
;
669 fprintf (f
, " cross_module");
671 if (hints
& INLINE_HINT_declared_inline
)
673 hints
&= ~INLINE_HINT_declared_inline
;
674 fprintf (f
, " declared_inline");
676 if (hints
& INLINE_HINT_array_index
)
678 hints
&= ~INLINE_HINT_array_index
;
679 fprintf (f
, " array_index");
681 if (hints
& INLINE_HINT_known_hot
)
683 hints
&= ~INLINE_HINT_known_hot
;
684 fprintf (f
, " known_hot");
690 /* Record SIZE and TIME under condition PRED into the inline summary. */
693 account_size_time (struct inline_summary
*summary
, int size
, int time
,
694 struct predicate
*pred
)
700 if (false_predicate_p (pred
))
703 /* We need to create initial empty unconitional clause, but otherwie
704 we don't need to account empty times and sizes. */
705 if (!size
&& !time
&& summary
->entry
)
708 /* Watch overflow that might result from insane profiles. */
709 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
710 time
= MAX_TIME
* INLINE_TIME_SCALE
;
711 gcc_assert (time
>= 0);
713 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
714 if (predicates_equal_p (&e
->predicate
, pred
))
723 e
= &(*summary
->entry
)[0];
724 gcc_assert (!e
->predicate
.clause
[0]);
725 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
727 "\t\tReached limit on number of entries, "
728 "ignoring the predicate.");
730 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
733 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
734 ((double) size
) / INLINE_SIZE_SCALE
,
735 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
736 dump_predicate (dump_file
, summary
->conds
, pred
);
740 struct size_time_entry new_entry
;
741 new_entry
.size
= size
;
742 new_entry
.time
= time
;
743 new_entry
.predicate
= *pred
;
744 vec_safe_push (summary
->entry
, new_entry
);
750 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
751 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
755 /* We proved E to be unreachable, redirect it to __bultin_unreachable. */
757 static struct cgraph_edge
*
758 redirect_to_unreachable (struct cgraph_edge
*e
)
760 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
761 struct cgraph_node
*target
= cgraph_node::get_create
762 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
));
765 e
= e
->resolve_speculation (target
->decl
);
767 e
->make_direct (target
);
769 e
->redirect_callee (target
);
770 struct inline_edge_summary
*es
= inline_edge_summary (e
);
771 e
->inline_failed
= CIF_UNREACHABLE
;
774 es
->call_stmt_size
= 0;
775 es
->call_stmt_time
= 0;
777 callee
->remove_symbol_and_inline_clones ();
781 /* Set predicate for edge E. */
784 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
786 /* If the edge is determined to be never executed, redirect it
787 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
788 if (predicate
&& false_predicate_p (predicate
)
789 /* When handling speculative edges, we need to do the redirection
790 just once. Do it always on the direct edge, so we do not
791 attempt to resolve speculation while duplicating the edge. */
792 && (!e
->speculative
|| e
->callee
))
793 e
= redirect_to_unreachable (e
);
795 struct inline_edge_summary
*es
= inline_edge_summary (e
);
796 if (predicate
&& !true_predicate_p (predicate
))
799 es
->predicate
= edge_predicate_pool
.allocate ();
800 *es
->predicate
= *predicate
;
805 edge_predicate_pool
.remove (es
->predicate
);
806 es
->predicate
= NULL
;
810 /* Set predicate for hint *P. */
813 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
815 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
818 edge_predicate_pool
.remove (*p
);
824 *p
= edge_predicate_pool
.allocate ();
830 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
831 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
832 Return clause of possible truths. When INLINE_P is true, assume that we are
835 ERROR_MARK means compile time invariant. */
838 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
840 vec
<tree
> known_vals
,
841 vec
<ipa_agg_jump_function_p
>
844 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
845 struct inline_summary
*info
= inline_summaries
->get (node
);
849 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
854 /* We allow call stmt to have fewer arguments than the callee function
855 (especially for K&R style programs). So bound check here (we assume
856 known_aggs vector, if non-NULL, has the same length as
858 gcc_checking_assert (!known_aggs
.exists ()
859 || (known_vals
.length () == known_aggs
.length ()));
860 if (c
->operand_num
>= (int) known_vals
.length ())
862 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
868 struct ipa_agg_jump_function
*agg
;
870 if (c
->code
== CHANGED
872 && (known_vals
[c
->operand_num
] == error_mark_node
))
875 if (known_aggs
.exists ())
877 agg
= known_aggs
[c
->operand_num
];
878 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
885 val
= known_vals
[c
->operand_num
];
886 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
892 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
895 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
898 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
899 TYPE_SIZE (TREE_TYPE (val
)), 0))
901 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
904 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
907 if (res
&& integer_zerop (res
))
910 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
916 /* Work out what conditions might be true at invocation of E. */
919 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
920 clause_t
*clause_ptr
,
921 vec
<tree
> *known_vals_ptr
,
922 vec
<ipa_polymorphic_call_context
>
924 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
926 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
927 struct inline_summary
*info
= inline_summaries
->get (callee
);
928 vec
<tree
> known_vals
= vNULL
;
929 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
932 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
934 known_vals_ptr
->create (0);
935 if (known_contexts_ptr
)
936 known_contexts_ptr
->create (0);
938 if (ipa_node_params_sum
939 && !e
->call_stmt_cannot_inline_p
940 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
942 struct ipa_node_params
*parms_info
;
943 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
944 struct inline_edge_summary
*es
= inline_edge_summary (e
);
945 int i
, count
= ipa_get_cs_argument_count (args
);
947 if (e
->caller
->global
.inlined_to
)
948 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
950 parms_info
= IPA_NODE_REF (e
->caller
);
952 if (count
&& (info
->conds
|| known_vals_ptr
))
953 known_vals
.safe_grow_cleared (count
);
954 if (count
&& (info
->conds
|| known_aggs_ptr
))
955 known_aggs
.safe_grow_cleared (count
);
956 if (count
&& known_contexts_ptr
)
957 known_contexts_ptr
->safe_grow_cleared (count
);
959 for (i
= 0; i
< count
; i
++)
961 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
962 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
964 if (!cst
&& e
->call_stmt
965 && i
< (int)gimple_call_num_args (e
->call_stmt
))
967 cst
= gimple_call_arg (e
->call_stmt
, i
);
968 if (!is_gimple_min_invariant (cst
))
973 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
974 if (known_vals
.exists ())
977 else if (inline_p
&& !es
->param
[i
].change_prob
)
978 known_vals
[i
] = error_mark_node
;
980 if (known_contexts_ptr
)
981 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
983 /* TODO: When IPA-CP starts propagating and merging aggregate jump
984 functions, use its knowledge of the caller too, just like the
985 scalar case above. */
986 known_aggs
[i
] = &jf
->agg
;
989 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
990 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
992 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
994 if (count
&& (info
->conds
|| known_vals_ptr
))
995 known_vals
.safe_grow_cleared (count
);
996 for (i
= 0; i
< count
; i
++)
998 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
999 if (!is_gimple_min_invariant (cst
))
1002 known_vals
[i
] = cst
;
1007 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
1008 known_vals
, known_aggs
);
1011 *known_vals_ptr
= known_vals
;
1013 known_vals
.release ();
1016 *known_aggs_ptr
= known_aggs
;
1018 known_aggs
.release ();
1022 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
1025 inline_summary_alloc (void)
1027 if (!edge_removal_hook_holder
)
1028 edge_removal_hook_holder
=
1029 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1030 if (!edge_duplication_hook_holder
)
1031 edge_duplication_hook_holder
=
1032 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1034 if (!inline_summaries
)
1035 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1037 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1038 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1041 /* We are called multiple time for given function; clear
1042 data from previous run so they are not cumulated. */
1045 reset_inline_edge_summary (struct cgraph_edge
*e
)
1047 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1049 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1051 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1053 edge_predicate_pool
.remove (es
->predicate
);
1054 es
->predicate
= NULL
;
1055 es
->param
.release ();
1059 /* We are called multiple time for given function; clear
1060 data from previous run so they are not cumulated. */
1063 reset_inline_summary (struct cgraph_node
*node
,
1064 inline_summary
*info
)
1066 struct cgraph_edge
*e
;
1068 info
->self_size
= info
->self_time
= 0;
1069 info
->estimated_stack_size
= 0;
1070 info
->estimated_self_stack_size
= 0;
1071 info
->stack_frame_offset
= 0;
1076 if (info
->loop_iterations
)
1078 edge_predicate_pool
.remove (info
->loop_iterations
);
1079 info
->loop_iterations
= NULL
;
1081 if (info
->loop_stride
)
1083 edge_predicate_pool
.remove (info
->loop_stride
);
1084 info
->loop_stride
= NULL
;
1086 if (info
->array_index
)
1088 edge_predicate_pool
.remove (info
->array_index
);
1089 info
->array_index
= NULL
;
1091 vec_free (info
->conds
);
1092 vec_free (info
->entry
);
1093 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1094 reset_inline_edge_summary (e
);
1095 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1096 reset_inline_edge_summary (e
);
1099 /* Hook that is called by cgraph.c when a node is removed. */
1102 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1104 reset_inline_summary (node
, info
);
1107 /* Remap predicate P of former function to be predicate of duplicated function.
1108 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1109 INFO is inline summary of the duplicated node. */
1111 static struct predicate
1112 remap_predicate_after_duplication (struct predicate
*p
,
1113 clause_t possible_truths
,
1114 struct inline_summary
*info
)
1116 struct predicate new_predicate
= true_predicate ();
1118 for (j
= 0; p
->clause
[j
]; j
++)
1119 if (!(possible_truths
& p
->clause
[j
]))
1121 new_predicate
= false_predicate ();
1125 add_clause (info
->conds
, &new_predicate
,
1126 possible_truths
& p
->clause
[j
]);
1127 return new_predicate
;
1130 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1131 Additionally care about allocating new memory slot for updated predicate
1132 and set it to NULL when it becomes true or false (and thus uninteresting).
1136 remap_hint_predicate_after_duplication (struct predicate
**p
,
1137 clause_t possible_truths
,
1138 struct inline_summary
*info
)
1140 struct predicate new_predicate
;
1145 new_predicate
= remap_predicate_after_duplication (*p
,
1146 possible_truths
, info
);
1147 /* We do not want to free previous predicate; it is used by node origin. */
1149 set_hint_predicate (p
, new_predicate
);
1153 /* Hook that is called by cgraph.c when a node is duplicated. */
1155 inline_summary_t::duplicate (cgraph_node
*src
,
1158 inline_summary
*info
)
1160 inline_summary_alloc ();
1161 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1162 /* TODO: as an optimization, we may avoid copying conditions
1163 that are known to be false or true. */
1164 info
->conds
= vec_safe_copy (info
->conds
);
1166 /* When there are any replacements in the function body, see if we can figure
1167 out that something was optimized out. */
1168 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1170 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1171 /* Use SRC parm info since it may not be copied yet. */
1172 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1173 vec
<tree
> known_vals
= vNULL
;
1174 int count
= ipa_get_param_count (parms_info
);
1176 clause_t possible_truths
;
1177 struct predicate true_pred
= true_predicate ();
1179 int optimized_out_size
= 0;
1180 bool inlined_to_p
= false;
1181 struct cgraph_edge
*edge
, *next
;
1184 known_vals
.safe_grow_cleared (count
);
1185 for (i
= 0; i
< count
; i
++)
1187 struct ipa_replace_map
*r
;
1189 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1191 if (((!r
->old_tree
&& r
->parm_num
== i
)
1192 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1193 && r
->replace_p
&& !r
->ref_p
)
1195 known_vals
[i
] = r
->new_tree
;
1200 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1203 known_vals
.release ();
1205 account_size_time (info
, 0, 0, &true_pred
);
1207 /* Remap size_time vectors.
1208 Simplify the predicate by prunning out alternatives that are known
1210 TODO: as on optimization, we can also eliminate conditions known
1212 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1214 struct predicate new_predicate
;
1215 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1218 if (false_predicate_p (&new_predicate
))
1219 optimized_out_size
+= e
->size
;
1221 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1224 /* Remap edge predicates with the same simplification as above.
1225 Also copy constantness arrays. */
1226 for (edge
= dst
->callees
; edge
; edge
= next
)
1228 struct predicate new_predicate
;
1229 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1230 next
= edge
->next_callee
;
1232 if (!edge
->inline_failed
)
1233 inlined_to_p
= true;
1236 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1239 if (false_predicate_p (&new_predicate
)
1240 && !false_predicate_p (es
->predicate
))
1241 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1242 edge_set_predicate (edge
, &new_predicate
);
1245 /* Remap indirect edge predicates with the same simplificaiton as above.
1246 Also copy constantness arrays. */
1247 for (edge
= dst
->indirect_calls
; edge
; edge
= next
)
1249 struct predicate new_predicate
;
1250 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1251 next
= edge
->next_callee
;
1253 gcc_checking_assert (edge
->inline_failed
);
1256 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1259 if (false_predicate_p (&new_predicate
)
1260 && !false_predicate_p (es
->predicate
))
1261 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1262 edge_set_predicate (edge
, &new_predicate
);
1264 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1265 possible_truths
, info
);
1266 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1267 possible_truths
, info
);
1268 remap_hint_predicate_after_duplication (&info
->array_index
,
1269 possible_truths
, info
);
1271 /* If inliner or someone after inliner will ever start producing
1272 non-trivial clones, we will get trouble with lack of information
1273 about updating self sizes, because size vectors already contains
1274 sizes of the calees. */
1275 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1279 info
->entry
= vec_safe_copy (info
->entry
);
1280 if (info
->loop_iterations
)
1282 predicate p
= *info
->loop_iterations
;
1283 info
->loop_iterations
= NULL
;
1284 set_hint_predicate (&info
->loop_iterations
, p
);
1286 if (info
->loop_stride
)
1288 predicate p
= *info
->loop_stride
;
1289 info
->loop_stride
= NULL
;
1290 set_hint_predicate (&info
->loop_stride
, p
);
1292 if (info
->array_index
)
1294 predicate p
= *info
->array_index
;
1295 info
->array_index
= NULL
;
1296 set_hint_predicate (&info
->array_index
, p
);
1299 if (!dst
->global
.inlined_to
)
1300 inline_update_overall_summary (dst
);
1304 /* Hook that is called by cgraph.c when a node is duplicated. */
1307 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1308 struct cgraph_edge
*dst
,
1309 ATTRIBUTE_UNUSED
void *data
)
1311 struct inline_edge_summary
*info
;
1312 struct inline_edge_summary
*srcinfo
;
1313 inline_summary_alloc ();
1314 info
= inline_edge_summary (dst
);
1315 srcinfo
= inline_edge_summary (src
);
1316 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1317 info
->predicate
= NULL
;
1318 edge_set_predicate (dst
, srcinfo
->predicate
);
1319 info
->param
= srcinfo
->param
.copy ();
1320 if (!dst
->indirect_unknown_callee
&& src
->indirect_unknown_callee
)
1322 info
->call_stmt_size
-= (eni_size_weights
.indirect_call_cost
1323 - eni_size_weights
.call_cost
);
1324 info
->call_stmt_time
-= (eni_time_weights
.indirect_call_cost
1325 - eni_time_weights
.call_cost
);
1330 /* Keep edge cache consistent across edge removal. */
1333 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1334 void *data ATTRIBUTE_UNUSED
)
1336 if (edge_growth_cache
.exists ())
1337 reset_edge_growth_cache (edge
);
1338 reset_inline_edge_summary (edge
);
1342 /* Initialize growth caches. */
1345 initialize_growth_caches (void)
1347 if (symtab
->edges_max_uid
)
1348 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1352 /* Free growth caches. */
1355 free_growth_caches (void)
1357 edge_growth_cache
.release ();
1361 /* Dump edge summaries associated to NODE and recursively to all clones.
1362 Indent by INDENT. */
1365 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1366 struct inline_summary
*info
)
1368 struct cgraph_edge
*edge
;
1369 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1371 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1372 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1376 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1377 " time: %2i callee size:%2i stack:%2i",
1378 indent
, "", callee
->name (), callee
->order
,
1379 !edge
->inline_failed
1380 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1381 indent
, "", es
->loop_depth
, edge
->frequency
,
1382 es
->call_stmt_size
, es
->call_stmt_time
,
1383 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1384 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1388 fprintf (f
, " predicate: ");
1389 dump_predicate (f
, info
->conds
, es
->predicate
);
1393 if (es
->param
.exists ())
1394 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1396 int prob
= es
->param
[i
].change_prob
;
1399 fprintf (f
, "%*s op%i is compile time invariant\n",
1401 else if (prob
!= REG_BR_PROB_BASE
)
1402 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1403 prob
* 100.0 / REG_BR_PROB_BASE
);
1405 if (!edge
->inline_failed
)
1407 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1408 " callee size %i\n",
1410 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1411 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1412 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1413 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1416 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1418 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1419 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1423 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1426 fprintf (f
, "predicate: ");
1427 dump_predicate (f
, info
->conds
, es
->predicate
);
1436 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1438 if (node
->definition
)
1440 struct inline_summary
*s
= inline_summaries
->get (node
);
1443 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1445 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1446 fprintf (f
, " always_inline");
1448 fprintf (f
, " inlinable");
1449 if (s
->contains_cilk_spawn
)
1450 fprintf (f
, " contains_cilk_spawn");
1451 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1452 fprintf (f
, " global time: %i\n", s
->time
);
1453 fprintf (f
, " self size: %i\n", s
->self_size
);
1454 fprintf (f
, " global size: %i\n", s
->size
);
1455 fprintf (f
, " min size: %i\n", s
->min_size
);
1456 fprintf (f
, " self stack: %i\n",
1457 (int) s
->estimated_self_stack_size
);
1458 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1460 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1462 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1463 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1465 fprintf (f
, " size:%f, time:%f, predicate:",
1466 (double) e
->size
/ INLINE_SIZE_SCALE
,
1467 (double) e
->time
/ INLINE_TIME_SCALE
);
1468 dump_predicate (f
, s
->conds
, &e
->predicate
);
1470 if (s
->loop_iterations
)
1472 fprintf (f
, " loop iterations:");
1473 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1477 fprintf (f
, " loop stride:");
1478 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1482 fprintf (f
, " array index:");
1483 dump_predicate (f
, s
->conds
, s
->array_index
);
1485 fprintf (f
, " calls:\n");
1486 dump_inline_edge_summary (f
, 4, node
, s
);
1492 debug_inline_summary (struct cgraph_node
*node
)
1494 dump_inline_summary (stderr
, node
);
1498 dump_inline_summaries (FILE *f
)
1500 struct cgraph_node
*node
;
1502 FOR_EACH_DEFINED_FUNCTION (node
)
1503 if (!node
->global
.inlined_to
)
1504 dump_inline_summary (f
, node
);
1507 /* Give initial reasons why inlining would fail on EDGE. This gets either
1508 nullified or usually overwritten by more precise reasons later. */
1511 initialize_inline_failed (struct cgraph_edge
*e
)
1513 struct cgraph_node
*callee
= e
->callee
;
1515 if (e
->indirect_unknown_callee
)
1516 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1517 else if (!callee
->definition
)
1518 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1519 else if (callee
->local
.redefined_extern_inline
)
1520 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1521 else if (e
->call_stmt_cannot_inline_p
)
1522 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1523 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1524 /* We can't inline if the function is spawing a function. */
1525 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1527 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1530 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1531 boolean variable pointed to by DATA. */
1534 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1537 bool *b
= (bool *) data
;
1542 /* If OP refers to value of function parameter, return the corresponding
1546 unmodified_parm_1 (gimple stmt
, tree op
)
1548 /* SSA_NAME referring to parm default def? */
1549 if (TREE_CODE (op
) == SSA_NAME
1550 && SSA_NAME_IS_DEFAULT_DEF (op
)
1551 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1552 return SSA_NAME_VAR (op
);
1553 /* Non-SSA parm reference? */
1554 if (TREE_CODE (op
) == PARM_DECL
)
1556 bool modified
= false;
1559 ao_ref_init (&refd
, op
);
1560 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1568 /* If OP refers to value of function parameter, return the corresponding
1569 parameter. Also traverse chains of SSA register assignments. */
1572 unmodified_parm (gimple stmt
, tree op
)
1574 tree res
= unmodified_parm_1 (stmt
, op
);
1578 if (TREE_CODE (op
) == SSA_NAME
1579 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1580 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1581 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1582 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1586 /* If OP refers to a value of a function parameter or value loaded from an
1587 aggregate passed to a parameter (either by value or reference), return TRUE
1588 and store the number of the parameter to *INDEX_P and information whether
1589 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1590 the function parameters, STMT is the statement in which OP is used or
1594 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1595 gimple stmt
, tree op
, int *index_p
,
1596 struct agg_position_info
*aggpos
)
1598 tree res
= unmodified_parm_1 (stmt
, op
);
1600 gcc_checking_assert (aggpos
);
1603 *index_p
= ipa_get_param_decl_index (info
, res
);
1606 aggpos
->agg_contents
= false;
1607 aggpos
->by_ref
= false;
1611 if (TREE_CODE (op
) == SSA_NAME
)
1613 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1614 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1616 stmt
= SSA_NAME_DEF_STMT (op
);
1617 op
= gimple_assign_rhs1 (stmt
);
1618 if (!REFERENCE_CLASS_P (op
))
1619 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1623 aggpos
->agg_contents
= true;
1624 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1628 /* See if statement might disappear after inlining.
1629 0 - means not eliminated
1630 1 - half of statements goes away
1631 2 - for sure it is eliminated.
1632 We are not terribly sophisticated, basically looking for simple abstraction
1633 penalty wrappers. */
1636 eliminated_by_inlining_prob (gimple stmt
)
1638 enum gimple_code code
= gimple_code (stmt
);
1639 enum tree_code rhs_code
;
1649 if (gimple_num_ops (stmt
) != 2)
1652 rhs_code
= gimple_assign_rhs_code (stmt
);
1654 /* Casts of parameters, loads from parameters passed by reference
1655 and stores to return value or parameters are often free after
1656 inlining dua to SRA and further combining.
1657 Assume that half of statements goes away. */
1658 if (CONVERT_EXPR_CODE_P (rhs_code
)
1659 || rhs_code
== VIEW_CONVERT_EXPR
1660 || rhs_code
== ADDR_EXPR
1661 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1663 tree rhs
= gimple_assign_rhs1 (stmt
);
1664 tree lhs
= gimple_assign_lhs (stmt
);
1665 tree inner_rhs
= get_base_address (rhs
);
1666 tree inner_lhs
= get_base_address (lhs
);
1667 bool rhs_free
= false;
1668 bool lhs_free
= false;
1675 /* Reads of parameter are expected to be free. */
1676 if (unmodified_parm (stmt
, inner_rhs
))
1678 /* Match expressions of form &this->field. Those will most likely
1679 combine with something upstream after inlining. */
1680 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1682 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1683 if (TREE_CODE (op
) == PARM_DECL
)
1685 else if (TREE_CODE (op
) == MEM_REF
1686 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1690 /* When parameter is not SSA register because its address is taken
1691 and it is just copied into one, the statement will be completely
1692 free after inlining (we will copy propagate backward). */
1693 if (rhs_free
&& is_gimple_reg (lhs
))
1696 /* Reads of parameters passed by reference
1697 expected to be free (i.e. optimized out after inlining). */
1698 if (TREE_CODE (inner_rhs
) == MEM_REF
1699 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1702 /* Copying parameter passed by reference into gimple register is
1703 probably also going to copy propagate, but we can't be quite
1705 if (rhs_free
&& is_gimple_reg (lhs
))
1708 /* Writes to parameters, parameters passed by value and return value
1709 (either dirrectly or passed via invisible reference) are free.
1711 TODO: We ought to handle testcase like
1712 struct a {int a,b;};
1714 retrurnsturct (void)
1720 This translate into:
1735 For that we either need to copy ipa-split logic detecting writes
1737 if (TREE_CODE (inner_lhs
) == PARM_DECL
1738 || TREE_CODE (inner_lhs
) == RESULT_DECL
1739 || (TREE_CODE (inner_lhs
) == MEM_REF
1740 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1741 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1742 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1743 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1745 0))) == RESULT_DECL
))))
1748 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1750 if (lhs_free
&& rhs_free
)
1760 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1761 predicates to the CFG edges. */
1764 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1765 struct inline_summary
*summary
,
1771 struct agg_position_info aggpos
;
1772 enum tree_code code
, inverted_code
;
1778 last
= last_stmt (bb
);
1779 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1781 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1783 op
= gimple_cond_lhs (last
);
1784 /* TODO: handle conditionals like
1787 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1789 code
= gimple_cond_code (last
);
1790 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1792 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1794 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1795 ? code
: inverted_code
);
1796 /* invert_tree_comparison will return ERROR_MARK on FP
1797 comparsions that are not EQ/NE instead of returning proper
1798 unordered one. Be sure it is not confused with NON_CONSTANT. */
1799 if (this_code
!= ERROR_MARK
)
1801 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1803 gimple_cond_rhs (last
));
1804 e
->aux
= edge_predicate_pool
.allocate ();
1805 *(struct predicate
*) e
->aux
= p
;
1810 if (TREE_CODE (op
) != SSA_NAME
)
1813 if (builtin_constant_p (op))
1817 Here we can predicate nonconstant_code. We can't
1818 really handle constant_code since we have no predicate
1819 for this and also the constant code is not known to be
1820 optimized away when inliner doen't see operand is constant.
1821 Other optimizers might think otherwise. */
1822 if (gimple_cond_code (last
) != NE_EXPR
1823 || !integer_zerop (gimple_cond_rhs (last
)))
1825 set_stmt
= SSA_NAME_DEF_STMT (op
);
1826 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1827 || gimple_call_num_args (set_stmt
) != 1)
1829 op2
= gimple_call_arg (set_stmt
, 0);
1830 if (!unmodified_parm_or_parm_agg_item
1831 (info
, set_stmt
, op2
, &index
, &aggpos
))
1833 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1835 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1836 IS_NOT_CONSTANT
, NULL_TREE
);
1837 e
->aux
= edge_predicate_pool
.allocate ();
1838 *(struct predicate
*) e
->aux
= p
;
1843 /* If BB ends by a switch we can turn into predicates, attach corresponding
1844 predicates to the CFG edges. */
1847 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1848 struct inline_summary
*summary
,
1854 struct agg_position_info aggpos
;
1860 lastg
= last_stmt (bb
);
1861 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1863 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1864 op
= gimple_switch_index (last
);
1865 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1868 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1870 e
->aux
= edge_predicate_pool
.allocate ();
1871 *(struct predicate
*) e
->aux
= false_predicate ();
1873 n
= gimple_switch_num_labels (last
);
1874 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1876 tree cl
= gimple_switch_label (last
, case_idx
);
1880 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1881 min
= CASE_LOW (cl
);
1882 max
= CASE_HIGH (cl
);
1884 /* For default we might want to construct predicate that none
1885 of cases is met, but it is bit hard to do not having negations
1886 of conditionals handy. */
1888 p
= true_predicate ();
1890 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1893 struct predicate p1
, p2
;
1894 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1895 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1896 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1898 *(struct predicate
*) e
->aux
1899 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1904 /* For each BB in NODE attach to its AUX pointer predicate under
1905 which it is executable. */
1908 compute_bb_predicates (struct cgraph_node
*node
,
1909 struct ipa_node_params
*parms_info
,
1910 struct inline_summary
*summary
)
1912 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1916 FOR_EACH_BB_FN (bb
, my_function
)
1918 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1919 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1922 /* Entry block is always executable. */
1923 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1924 = edge_predicate_pool
.allocate ();
1925 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1926 = true_predicate ();
1928 /* A simple dataflow propagation of predicates forward in the CFG.
1929 TODO: work in reverse postorder. */
1933 FOR_EACH_BB_FN (bb
, my_function
)
1935 struct predicate p
= false_predicate ();
1938 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1942 struct predicate this_bb_predicate
1943 = *(struct predicate
*) e
->src
->aux
;
1946 = and_predicates (summary
->conds
, &this_bb_predicate
,
1947 (struct predicate
*) e
->aux
);
1948 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1949 if (true_predicate_p (&p
))
1953 if (false_predicate_p (&p
))
1954 gcc_assert (!bb
->aux
);
1960 bb
->aux
= edge_predicate_pool
.allocate ();
1961 *((struct predicate
*) bb
->aux
) = p
;
1963 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1965 /* This OR operation is needed to ensure monotonous data flow
1966 in the case we hit the limit on number of clauses and the
1967 and/or operations above give approximate answers. */
1968 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1969 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1972 *((struct predicate
*) bb
->aux
) = p
;
1981 /* We keep info about constantness of SSA names. */
1983 typedef struct predicate predicate_t
;
1984 /* Return predicate specifying when the STMT might have result that is not
1985 a compile time constant. */
1987 static struct predicate
1988 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1989 struct inline_summary
*summary
,
1991 vec
<predicate_t
> nonconstant_names
)
1996 while (UNARY_CLASS_P (expr
))
1997 expr
= TREE_OPERAND (expr
, 0);
1999 parm
= unmodified_parm (NULL
, expr
);
2000 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2001 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2002 if (is_gimple_min_invariant (expr
))
2003 return false_predicate ();
2004 if (TREE_CODE (expr
) == SSA_NAME
)
2005 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
2006 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
2008 struct predicate p1
= will_be_nonconstant_expr_predicate
2009 (info
, summary
, TREE_OPERAND (expr
, 0),
2011 struct predicate p2
;
2012 if (true_predicate_p (&p1
))
2014 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2015 TREE_OPERAND (expr
, 1),
2017 return or_predicates (summary
->conds
, &p1
, &p2
);
2019 else if (TREE_CODE (expr
) == COND_EXPR
)
2021 struct predicate p1
= will_be_nonconstant_expr_predicate
2022 (info
, summary
, TREE_OPERAND (expr
, 0),
2024 struct predicate p2
;
2025 if (true_predicate_p (&p1
))
2027 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2028 TREE_OPERAND (expr
, 1),
2030 if (true_predicate_p (&p2
))
2032 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2033 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2034 TREE_OPERAND (expr
, 2),
2036 return or_predicates (summary
->conds
, &p1
, &p2
);
2043 return false_predicate ();
2047 /* Return predicate specifying when the STMT might have result that is not
2048 a compile time constant. */
2050 static struct predicate
2051 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2052 struct inline_summary
*summary
,
2054 vec
<predicate_t
> nonconstant_names
)
2056 struct predicate p
= true_predicate ();
2059 struct predicate op_non_const
;
2062 struct agg_position_info aggpos
;
2064 /* What statments might be optimized away
2065 when their arguments are constant. */
2066 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2067 && gimple_code (stmt
) != GIMPLE_COND
2068 && gimple_code (stmt
) != GIMPLE_SWITCH
2069 && (gimple_code (stmt
) != GIMPLE_CALL
2070 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2073 /* Stores will stay anyway. */
2074 if (gimple_store_p (stmt
))
2077 is_load
= gimple_assign_load_p (stmt
);
2079 /* Loads can be optimized when the value is known. */
2083 gcc_assert (gimple_assign_single_p (stmt
));
2084 op
= gimple_assign_rhs1 (stmt
);
2085 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2092 /* See if we understand all operands before we start
2093 adding conditionals. */
2094 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2096 tree parm
= unmodified_parm (stmt
, use
);
2097 /* For arguments we can build a condition. */
2098 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2100 if (TREE_CODE (use
) != SSA_NAME
)
2102 /* If we know when operand is constant,
2103 we still can say something useful. */
2104 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2111 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2113 op_non_const
= false_predicate ();
2114 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2116 tree parm
= unmodified_parm (stmt
, use
);
2119 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2121 if (index
!= base_index
)
2122 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2127 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2128 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2130 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2131 && gimple_op (stmt
, 0)
2132 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2133 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2135 return op_non_const
;
2138 struct record_modified_bb_info
2144 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2145 set except for info->stmt. */
2148 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2150 struct record_modified_bb_info
*info
=
2151 (struct record_modified_bb_info
*) data
;
2152 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2154 bitmap_set_bit (info
->bb_set
,
2155 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2156 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2157 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2161 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2162 will change since last invocation of STMT.
2164 Value 0 is reserved for compile time invariants.
2165 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2166 ought to be REG_BR_PROB_BASE / estimated_iters. */
2169 param_change_prob (gimple stmt
, int i
)
2171 tree op
= gimple_call_arg (stmt
, i
);
2172 basic_block bb
= gimple_bb (stmt
);
2175 /* Global invariants neve change. */
2176 if (is_gimple_min_invariant (op
))
2178 /* We would have to do non-trivial analysis to really work out what
2179 is the probability of value to change (i.e. when init statement
2180 is in a sibling loop of the call).
2182 We do an conservative estimate: when call is executed N times more often
2183 than the statement defining value, we take the frequency 1/N. */
2184 if (TREE_CODE (op
) == SSA_NAME
)
2189 return REG_BR_PROB_BASE
;
2191 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2192 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2194 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2198 if (init_freq
< bb
->frequency
)
2199 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2201 return REG_BR_PROB_BASE
;
2204 base
= get_base_address (op
);
2209 struct record_modified_bb_info info
;
2212 tree init
= ctor_for_folding (base
);
2214 if (init
!= error_mark_node
)
2217 return REG_BR_PROB_BASE
;
2218 ao_ref_init (&refd
, op
);
2220 info
.bb_set
= BITMAP_ALLOC (NULL
);
2221 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2223 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2225 BITMAP_FREE (info
.bb_set
);
2226 return REG_BR_PROB_BASE
;
2229 /* Assume that every memory is initialized at entry.
2230 TODO: Can we easilly determine if value is always defined
2231 and thus we may skip entry block? */
2232 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2233 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2237 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2238 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2240 BITMAP_FREE (info
.bb_set
);
2241 if (max
< bb
->frequency
)
2242 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2244 return REG_BR_PROB_BASE
;
2246 return REG_BR_PROB_BASE
;
2249 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2250 sub-graph and if the predicate the condition depends on is known. If so,
2251 return true and store the pointer the predicate in *P. */
2254 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2255 inline_summary
*summary
, basic_block bb
,
2256 struct predicate
*p
,
2257 vec
<predicate_t
> nonconstant_names
)
2261 basic_block first_bb
= NULL
;
2264 if (single_pred_p (bb
))
2266 *p
= false_predicate ();
2270 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2272 if (single_succ_p (e
->src
))
2274 if (!single_pred_p (e
->src
))
2277 first_bb
= single_pred (e
->src
);
2278 else if (single_pred (e
->src
) != first_bb
)
2285 else if (e
->src
!= first_bb
)
2293 stmt
= last_stmt (first_bb
);
2295 || gimple_code (stmt
) != GIMPLE_COND
2296 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2299 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2300 gimple_cond_lhs (stmt
),
2302 if (true_predicate_p (p
))
2308 /* Given a PHI statement in a function described by inline properties SUMMARY
2309 and *P being the predicate describing whether the selected PHI argument is
2310 known, store a predicate for the result of the PHI statement into
2311 NONCONSTANT_NAMES, if possible. */
2314 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2315 struct predicate
*p
,
2316 vec
<predicate_t
> nonconstant_names
)
2320 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2322 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2323 if (!is_gimple_min_invariant (arg
))
2325 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2326 *p
= or_predicates (summary
->conds
, p
,
2327 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2328 if (true_predicate_p (p
))
2333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2335 fprintf (dump_file
, "\t\tphi predicate: ");
2336 dump_predicate (dump_file
, summary
->conds
, p
);
2338 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2341 /* Return predicate specifying when array index in access OP becomes non-constant. */
2343 static struct predicate
2344 array_index_predicate (inline_summary
*info
,
2345 vec
< predicate_t
> nonconstant_names
, tree op
)
2347 struct predicate p
= false_predicate ();
2348 while (handled_component_p (op
))
2350 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2352 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2353 p
= or_predicates (info
->conds
, &p
,
2354 &nonconstant_names
[SSA_NAME_VERSION
2355 (TREE_OPERAND (op
, 1))]);
2357 op
= TREE_OPERAND (op
, 0);
2362 /* For a typical usage of __builtin_expect (a<b, 1), we
2363 may introduce an extra relation stmt:
2364 With the builtin, we have
2367 t3 = __builtin_expect (t2, 1);
2370 Without the builtin, we have
2373 This affects the size/time estimation and may have
2374 an impact on the earlier inlining.
2375 Here find this pattern and fix it up later. */
2378 find_foldable_builtin_expect (basic_block bb
)
2380 gimple_stmt_iterator bsi
;
2382 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2384 gimple stmt
= gsi_stmt (bsi
);
2385 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2386 || (is_gimple_call (stmt
)
2387 && gimple_call_internal_p (stmt
)
2388 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2390 tree var
= gimple_call_lhs (stmt
);
2391 tree arg
= gimple_call_arg (stmt
, 0);
2392 use_operand_p use_p
;
2399 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2401 while (TREE_CODE (arg
) == SSA_NAME
)
2403 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2404 if (!is_gimple_assign (stmt_tmp
))
2406 switch (gimple_assign_rhs_code (stmt_tmp
))
2425 arg
= gimple_assign_rhs1 (stmt_tmp
);
2428 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2429 && gimple_code (use_stmt
) == GIMPLE_COND
)
2436 /* Return true when the basic blocks contains only clobbers followed by RESX.
2437 Such BBs are kept around to make removal of dead stores possible with
2438 presence of EH and will be optimized out by optimize_clobbers later in the
2441 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2442 that can be clobber only, too.. When it is false, the RESX is not necessary
2443 on the end of basic block. */
2446 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2448 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2454 if (gsi_end_p (gsi
))
2456 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2460 else if (!single_succ_p (bb
))
2463 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2465 gimple stmt
= gsi_stmt (gsi
);
2466 if (is_gimple_debug (stmt
))
2468 if (gimple_clobber_p (stmt
))
2470 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2475 /* See if all predecestors are either throws or clobber only BBs. */
2476 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2477 if (!(e
->flags
& EDGE_EH
)
2478 && !clobber_only_eh_bb_p (e
->src
, false))
2484 /* Compute function body size parameters for NODE.
2485 When EARLY is true, we compute only simple summaries without
2486 non-trivial predicates to drive the early inliner. */
2489 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2492 /* Estimate static overhead for function prologue/epilogue and alignment. */
2494 /* Benefits are scaled by probability of elimination that is in range
2497 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2499 struct inline_summary
*info
= inline_summaries
->get (node
);
2500 struct predicate bb_predicate
;
2501 struct ipa_node_params
*parms_info
= NULL
;
2502 vec
<predicate_t
> nonconstant_names
= vNULL
;
2505 predicate array_index
= true_predicate ();
2506 gimple fix_builtin_expect_stmt
;
2511 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2512 so we can produce proper inline hints.
2514 When optimizing and analyzing for early inliner, initialize node params
2515 so we can produce correct BB predicates. */
2517 if (opt_for_fn (node
->decl
, optimize
))
2519 calculate_dominance_info (CDI_DOMINATORS
);
2521 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2524 ipa_check_create_node_params ();
2525 ipa_initialize_node_params (node
);
2528 if (ipa_node_params_sum
)
2530 parms_info
= IPA_NODE_REF (node
);
2531 nonconstant_names
.safe_grow_cleared
2532 (SSANAMES (my_function
)->length ());
2537 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2540 /* When we run into maximal number of entries, we assign everything to the
2541 constant truth case. Be sure to have it in list. */
2542 bb_predicate
= true_predicate ();
2543 account_size_time (info
, 0, 0, &bb_predicate
);
2545 bb_predicate
= not_inlined_predicate ();
2546 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2548 gcc_assert (my_function
&& my_function
->cfg
);
2550 compute_bb_predicates (node
, parms_info
, info
);
2551 gcc_assert (cfun
== my_function
);
2552 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2553 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2554 for (n
= 0; n
< nblocks
; n
++)
2556 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2557 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2558 if (clobber_only_eh_bb_p (bb
))
2560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2561 fprintf (dump_file
, "\n Ignoring BB %i;"
2562 " it will be optimized away by cleanup_clobbers\n",
2567 /* TODO: Obviously predicates can be propagated down across CFG. */
2571 bb_predicate
= *(struct predicate
*) bb
->aux
;
2573 bb_predicate
= false_predicate ();
2576 bb_predicate
= true_predicate ();
2578 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2580 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2581 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2584 if (parms_info
&& nonconstant_names
.exists ())
2586 struct predicate phi_predicate
;
2587 bool first_phi
= true;
2589 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2593 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2598 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2600 fprintf (dump_file
, " ");
2601 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2603 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2608 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2610 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2613 gimple stmt
= gsi_stmt (bsi
);
2614 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2615 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2617 struct predicate will_be_nonconstant
;
2619 /* This relation stmt should be folded after we remove
2620 buildin_expect call. Adjust the cost here. */
2621 if (stmt
== fix_builtin_expect_stmt
)
2627 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2629 fprintf (dump_file
, " ");
2630 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2631 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2632 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2636 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2638 struct predicate this_array_index
;
2640 array_index_predicate (info
, nonconstant_names
,
2641 gimple_assign_rhs1 (stmt
));
2642 if (!false_predicate_p (&this_array_index
))
2644 and_predicates (info
->conds
, &array_index
,
2647 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2649 struct predicate this_array_index
;
2651 array_index_predicate (info
, nonconstant_names
,
2652 gimple_get_lhs (stmt
));
2653 if (!false_predicate_p (&this_array_index
))
2655 and_predicates (info
->conds
, &array_index
,
2660 if (is_gimple_call (stmt
)
2661 && !gimple_call_internal_p (stmt
))
2663 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2664 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2666 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2667 resolved as constant. We however don't want to optimize
2668 out the cgraph edges. */
2669 if (nonconstant_names
.exists ()
2670 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2671 && gimple_call_lhs (stmt
)
2672 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2674 struct predicate false_p
= false_predicate ();
2675 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2678 if (ipa_node_params_sum
)
2680 int count
= gimple_call_num_args (stmt
);
2684 es
->param
.safe_grow_cleared (count
);
2685 for (i
= 0; i
< count
; i
++)
2687 int prob
= param_change_prob (stmt
, i
);
2688 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2689 es
->param
[i
].change_prob
= prob
;
2693 es
->call_stmt_size
= this_size
;
2694 es
->call_stmt_time
= this_time
;
2695 es
->loop_depth
= bb_loop_depth (bb
);
2696 edge_set_predicate (edge
, &bb_predicate
);
2699 /* TODO: When conditional jump or swithc is known to be constant, but
2700 we did not translate it into the predicates, we really can account
2701 just maximum of the possible paths. */
2704 = will_be_nonconstant_predicate (parms_info
, info
,
2705 stmt
, nonconstant_names
);
2706 if (this_time
|| this_size
)
2712 prob
= eliminated_by_inlining_prob (stmt
);
2713 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2715 "\t\t50%% will be eliminated by inlining\n");
2716 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2717 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2720 p
= and_predicates (info
->conds
, &bb_predicate
,
2721 &will_be_nonconstant
);
2723 p
= true_predicate ();
2725 if (!false_predicate_p (&p
)
2726 || (is_gimple_call (stmt
)
2727 && !false_predicate_p (&bb_predicate
)))
2731 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2732 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2735 /* We account everything but the calls. Calls have their own
2736 size/time info attached to cgraph edges. This is necessary
2737 in order to make the cost disappear after inlining. */
2738 if (!is_gimple_call (stmt
))
2742 struct predicate ip
= not_inlined_predicate ();
2743 ip
= and_predicates (info
->conds
, &ip
, &p
);
2744 account_size_time (info
, this_size
* prob
,
2745 this_time
* prob
, &ip
);
2748 account_size_time (info
, this_size
* (2 - prob
),
2749 this_time
* (2 - prob
), &p
);
2752 gcc_assert (time
>= 0);
2753 gcc_assert (size
>= 0);
2757 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2758 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2759 if (time
> MAX_TIME
)
2763 if (nonconstant_names
.exists () && !early
)
2766 predicate loop_iterations
= true_predicate ();
2767 predicate loop_stride
= true_predicate ();
2769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2770 flow_loops_dump (dump_file
, NULL
, 0);
2772 FOR_EACH_LOOP (loop
, 0)
2777 struct tree_niter_desc niter_desc
;
2778 basic_block
*body
= get_loop_body (loop
);
2779 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2781 exits
= get_loop_exit_edges (loop
);
2782 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2783 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2784 && !is_gimple_min_invariant (niter_desc
.niter
))
2786 predicate will_be_nonconstant
2787 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2790 if (!true_predicate_p (&will_be_nonconstant
))
2791 will_be_nonconstant
= and_predicates (info
->conds
,
2793 &will_be_nonconstant
);
2794 if (!true_predicate_p (&will_be_nonconstant
)
2795 && !false_predicate_p (&will_be_nonconstant
))
2796 /* This is slightly inprecise. We may want to represent each
2797 loop with independent predicate. */
2799 and_predicates (info
->conds
, &loop_iterations
,
2800 &will_be_nonconstant
);
2804 for (i
= 0; i
< loop
->num_nodes
; i
++)
2806 gimple_stmt_iterator gsi
;
2807 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2808 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2811 gimple stmt
= gsi_stmt (gsi
);
2816 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2818 predicate will_be_nonconstant
;
2821 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2822 || is_gimple_min_invariant (iv
.step
))
2825 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2828 if (!true_predicate_p (&will_be_nonconstant
))
2830 = and_predicates (info
->conds
,
2832 &will_be_nonconstant
);
2833 if (!true_predicate_p (&will_be_nonconstant
)
2834 && !false_predicate_p (&will_be_nonconstant
))
2835 /* This is slightly inprecise. We may want to represent
2836 each loop with independent predicate. */
2838 and_predicates (info
->conds
, &loop_stride
,
2839 &will_be_nonconstant
);
2845 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2847 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
, loop_stride
);
2850 FOR_ALL_BB_FN (bb
, my_function
)
2856 edge_predicate_pool
.remove ((predicate
*)bb
->aux
);
2858 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2861 edge_predicate_pool
.remove ((predicate
*) e
->aux
);
2865 inline_summaries
->get (node
)->self_time
= time
;
2866 inline_summaries
->get (node
)->self_size
= size
;
2867 nonconstant_names
.release ();
2868 if (opt_for_fn (node
->decl
, optimize
))
2871 loop_optimizer_finalize ();
2872 else if (!ipa_edge_args_vector
)
2873 ipa_free_all_node_params ();
2874 free_dominance_info (CDI_DOMINATORS
);
2878 fprintf (dump_file
, "\n");
2879 dump_inline_summary (dump_file
, node
);
2884 /* Compute parameters of functions used by inliner.
2885 EARLY is true when we compute parameters for the early inliner */
2888 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2890 HOST_WIDE_INT self_stack_size
;
2891 struct cgraph_edge
*e
;
2892 struct inline_summary
*info
;
2894 gcc_assert (!node
->global
.inlined_to
);
2896 inline_summary_alloc ();
2898 info
= inline_summaries
->get (node
);
2899 reset_inline_summary (node
, info
);
2901 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2902 Once this happen, we will need to more curefully predict call
2904 if (node
->thunk
.thunk_p
)
2906 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2907 struct predicate t
= true_predicate ();
2909 info
->inlinable
= 0;
2910 node
->callees
->call_stmt_cannot_inline_p
= true;
2911 node
->local
.can_change_signature
= false;
2912 es
->call_stmt_time
= 1;
2913 es
->call_stmt_size
= 1;
2914 account_size_time (info
, 0, 0, &t
);
2918 /* Even is_gimple_min_invariant rely on current_function_decl. */
2919 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2921 /* Estimate the stack size for the function if we're optimizing. */
2922 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2923 info
->estimated_self_stack_size
= self_stack_size
;
2924 info
->estimated_stack_size
= self_stack_size
;
2925 info
->stack_frame_offset
= 0;
2927 /* Can this function be inlined at all? */
2928 if (!opt_for_fn (node
->decl
, optimize
)
2929 && !lookup_attribute ("always_inline",
2930 DECL_ATTRIBUTES (node
->decl
)))
2931 info
->inlinable
= false;
2933 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2935 info
->contains_cilk_spawn
= fn_contains_cilk_spawn_p (cfun
);
2937 /* Type attributes can use parameter indices to describe them. */
2938 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2939 node
->local
.can_change_signature
= false;
2942 /* Otherwise, inlinable functions always can change signature. */
2943 if (info
->inlinable
)
2944 node
->local
.can_change_signature
= true;
2947 /* Functions calling builtin_apply can not change signature. */
2948 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2950 tree
cdecl = e
->callee
->decl
;
2951 if (DECL_BUILT_IN (cdecl)
2952 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2953 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2954 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2957 node
->local
.can_change_signature
= !e
;
2960 estimate_function_body_sizes (node
, early
);
2962 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2963 if (e
->callee
->comdat_local_p ())
2965 node
->calls_comdat_local
= (e
!= NULL
);
2967 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2968 info
->time
= info
->self_time
;
2969 info
->size
= info
->self_size
;
2970 info
->stack_frame_offset
= 0;
2971 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2972 #ifdef ENABLE_CHECKING
2973 inline_update_overall_summary (node
);
2974 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2981 /* Compute parameters of functions used by inliner using
2982 current_function_decl. */
2985 compute_inline_parameters_for_current (void)
2987 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2993 const pass_data pass_data_inline_parameters
=
2995 GIMPLE_PASS
, /* type */
2996 "inline_param", /* name */
2997 OPTGROUP_INLINE
, /* optinfo_flags */
2998 TV_INLINE_PARAMETERS
, /* tv_id */
2999 0, /* properties_required */
3000 0, /* properties_provided */
3001 0, /* properties_destroyed */
3002 0, /* todo_flags_start */
3003 0, /* todo_flags_finish */
3006 class pass_inline_parameters
: public gimple_opt_pass
3009 pass_inline_parameters (gcc::context
*ctxt
)
3010 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
3013 /* opt_pass methods: */
3014 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
3015 virtual unsigned int execute (function
*)
3017 return compute_inline_parameters_for_current ();
3020 }; // class pass_inline_parameters
3025 make_pass_inline_parameters (gcc::context
*ctxt
)
3027 return new pass_inline_parameters (ctxt
);
3031 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3032 KNOWN_CONTEXTS and KNOWN_AGGS. */
3035 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3036 int *size
, int *time
,
3037 vec
<tree
> known_vals
,
3038 vec
<ipa_polymorphic_call_context
> known_contexts
,
3039 vec
<ipa_agg_jump_function_p
> known_aggs
)
3042 struct cgraph_node
*callee
;
3043 struct inline_summary
*isummary
;
3044 enum availability avail
;
3047 if (!known_vals
.exists () && !known_contexts
.exists ())
3049 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3052 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3053 known_aggs
, &speculative
);
3054 if (!target
|| speculative
)
3057 /* Account for difference in cost between indirect and direct calls. */
3058 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3059 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3060 gcc_checking_assert (*time
>= 0);
3061 gcc_checking_assert (*size
>= 0);
3063 callee
= cgraph_node::get (target
);
3064 if (!callee
|| !callee
->definition
)
3066 callee
= callee
->function_symbol (&avail
);
3067 if (avail
< AVAIL_AVAILABLE
)
3069 isummary
= inline_summaries
->get (callee
);
3070 return isummary
->inlinable
;
3073 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3074 handle edge E with probability PROB.
3075 Set HINTS if edge may be devirtualized.
3076 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3080 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3083 vec
<tree
> known_vals
,
3084 vec
<ipa_polymorphic_call_context
> known_contexts
,
3085 vec
<ipa_agg_jump_function_p
> known_aggs
,
3086 inline_hints
*hints
)
3088 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3089 int call_size
= es
->call_stmt_size
;
3090 int call_time
= es
->call_stmt_time
;
3093 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3094 known_vals
, known_contexts
, known_aggs
)
3095 && hints
&& e
->maybe_hot_p ())
3096 *hints
|= INLINE_HINT_indirect_call
;
3097 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3100 *min_size
+= cur_size
;
3101 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3102 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3103 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3104 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3109 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3110 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3111 describe context of the call site. */
3114 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3115 int *min_size
, int *time
,
3116 inline_hints
*hints
,
3117 clause_t possible_truths
,
3118 vec
<tree
> known_vals
,
3119 vec
<ipa_polymorphic_call_context
> known_contexts
,
3120 vec
<ipa_agg_jump_function_p
> known_aggs
)
3122 struct cgraph_edge
*e
;
3123 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3125 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3127 /* Do not care about zero sized builtins. */
3128 if (e
->inline_failed
&& !es
->call_stmt_size
)
3130 gcc_checking_assert (!es
->call_stmt_time
);
3134 || evaluate_predicate (es
->predicate
, possible_truths
))
3136 if (e
->inline_failed
)
3138 /* Predicates of calls shall not use NOT_CHANGED codes,
3139 sowe do not need to compute probabilities. */
3140 estimate_edge_size_and_time (e
, size
,
3141 es
->predicate
? NULL
: min_size
,
3142 time
, REG_BR_PROB_BASE
,
3143 known_vals
, known_contexts
,
3147 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3150 known_vals
, known_contexts
,
3154 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3156 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3158 || evaluate_predicate (es
->predicate
, possible_truths
))
3159 estimate_edge_size_and_time (e
, size
,
3160 es
->predicate
? NULL
: min_size
,
3161 time
, REG_BR_PROB_BASE
,
3162 known_vals
, known_contexts
, known_aggs
,
3168 /* Estimate size and time needed to execute NODE assuming
3169 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3170 information about NODE's arguments. If non-NULL use also probability
3171 information present in INLINE_PARAM_SUMMARY vector.
3172 Additionally detemine hints determined by the context. Finally compute
3173 minimal size needed for the call that is independent on the call context and
3174 can be used for fast estimates. Return the values in RET_SIZE,
3175 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3178 estimate_node_size_and_time (struct cgraph_node
*node
,
3179 clause_t possible_truths
,
3180 vec
<tree
> known_vals
,
3181 vec
<ipa_polymorphic_call_context
> known_contexts
,
3182 vec
<ipa_agg_jump_function_p
> known_aggs
,
3183 int *ret_size
, int *ret_min_size
, int *ret_time
,
3184 inline_hints
*ret_hints
,
3185 vec
<inline_param_summary
>
3186 inline_param_summary
)
3188 struct inline_summary
*info
= inline_summaries
->get (node
);
3193 inline_hints hints
= 0;
3196 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3199 fprintf (dump_file
, " Estimating body: %s/%i\n"
3200 " Known to be false: ", node
->name (),
3203 for (i
= predicate_not_inlined_condition
;
3204 i
< (predicate_first_dynamic_condition
3205 + (int) vec_safe_length (info
->conds
)); i
++)
3206 if (!(possible_truths
& (1 << i
)))
3209 fprintf (dump_file
, ", ");
3211 dump_condition (dump_file
, info
->conds
, i
);
3215 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3216 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3219 gcc_checking_assert (e
->time
>= 0);
3220 gcc_checking_assert (time
>= 0);
3221 if (!inline_param_summary
.exists ())
3225 int prob
= predicate_probability (info
->conds
,
3228 inline_param_summary
);
3229 gcc_checking_assert (prob
>= 0);
3230 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3231 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3233 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3234 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3235 gcc_checking_assert (time
>= 0);
3238 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3239 min_size
= (*info
->entry
)[0].size
;
3240 gcc_checking_assert (size
>= 0);
3241 gcc_checking_assert (time
>= 0);
3243 if (info
->loop_iterations
3244 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3245 hints
|= INLINE_HINT_loop_iterations
;
3246 if (info
->loop_stride
3247 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3248 hints
|= INLINE_HINT_loop_stride
;
3249 if (info
->array_index
3250 && !evaluate_predicate (info
->array_index
, possible_truths
))
3251 hints
|= INLINE_HINT_array_index
;
3253 hints
|= INLINE_HINT_in_scc
;
3254 if (DECL_DECLARED_INLINE_P (node
->decl
))
3255 hints
|= INLINE_HINT_declared_inline
;
3257 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3258 known_vals
, known_contexts
, known_aggs
);
3259 gcc_checking_assert (size
>= 0);
3260 gcc_checking_assert (time
>= 0);
3261 time
= RDIV (time
, INLINE_TIME_SCALE
);
3262 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3263 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3266 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3272 *ret_min_size
= min_size
;
3279 /* Estimate size and time needed to execute callee of EDGE assuming that
3280 parameters known to be constant at caller of EDGE are propagated.
3281 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3282 and types for parameters. */
3285 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3286 vec
<tree
> known_vals
,
3287 vec
<ipa_polymorphic_call_context
>
3289 vec
<ipa_agg_jump_function_p
> known_aggs
,
3290 int *ret_size
, int *ret_time
,
3291 inline_hints
*hints
)
3295 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3297 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3298 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3301 /* Translate all conditions from callee representation into caller
3302 representation and symbolically evaluate predicate P into new predicate.
3304 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3305 is summary of function predicate P is from. OPERAND_MAP is array giving
3306 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3307 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3308 predicate under which callee is executed. OFFSET_MAP is an array of of
3309 offsets that need to be added to conditions, negative offset means that
3310 conditions relying on values passed by reference have to be discarded
3311 because they might not be preserved (and should be considered offset zero
3312 for other purposes). */
3314 static struct predicate
3315 remap_predicate (struct inline_summary
*info
,
3316 struct inline_summary
*callee_info
,
3317 struct predicate
*p
,
3318 vec
<int> operand_map
,
3319 vec
<int> offset_map
,
3320 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3323 struct predicate out
= true_predicate ();
3325 /* True predicate is easy. */
3326 if (true_predicate_p (p
))
3327 return *toplev_predicate
;
3328 for (i
= 0; p
->clause
[i
]; i
++)
3330 clause_t clause
= p
->clause
[i
];
3332 struct predicate clause_predicate
= false_predicate ();
3334 gcc_assert (i
< MAX_CLAUSES
);
3336 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3337 /* Do we have condition we can't disprove? */
3338 if (clause
& possible_truths
& (1 << cond
))
3340 struct predicate cond_predicate
;
3341 /* Work out if the condition can translate to predicate in the
3342 inlined function. */
3343 if (cond
>= predicate_first_dynamic_condition
)
3345 struct condition
*c
;
3347 c
= &(*callee_info
->conds
)[cond
3349 predicate_first_dynamic_condition
];
3350 /* See if we can remap condition operand to caller's operand.
3351 Otherwise give up. */
3352 if (!operand_map
.exists ()
3353 || (int) operand_map
.length () <= c
->operand_num
3354 || operand_map
[c
->operand_num
] == -1
3355 /* TODO: For non-aggregate conditions, adding an offset is
3356 basically an arithmetic jump function processing which
3357 we should support in future. */
3358 || ((!c
->agg_contents
|| !c
->by_ref
)
3359 && offset_map
[c
->operand_num
] > 0)
3360 || (c
->agg_contents
&& c
->by_ref
3361 && offset_map
[c
->operand_num
] < 0))
3362 cond_predicate
= true_predicate ();
3365 struct agg_position_info ap
;
3366 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3367 if (offset_delta
< 0)
3369 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3372 gcc_assert (!c
->agg_contents
3373 || c
->by_ref
|| offset_delta
== 0);
3374 ap
.offset
= c
->offset
+ offset_delta
;
3375 ap
.agg_contents
= c
->agg_contents
;
3376 ap
.by_ref
= c
->by_ref
;
3377 cond_predicate
= add_condition (info
,
3378 operand_map
[c
->operand_num
],
3379 &ap
, c
->code
, c
->val
);
3382 /* Fixed conditions remains same, construct single
3383 condition predicate. */
3386 cond_predicate
.clause
[0] = 1 << cond
;
3387 cond_predicate
.clause
[1] = 0;
3389 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3392 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3394 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3398 /* Update summary information of inline clones after inlining.
3399 Compute peak stack usage. */
3402 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3404 struct cgraph_edge
*e
;
3405 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3406 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3409 callee_info
->stack_frame_offset
3410 = caller_info
->stack_frame_offset
3411 + caller_info
->estimated_self_stack_size
;
3412 peak
= callee_info
->stack_frame_offset
3413 + callee_info
->estimated_self_stack_size
;
3414 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3415 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3416 ipa_propagate_frequency (node
);
3417 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3419 if (!e
->inline_failed
)
3420 inline_update_callee_summaries (e
->callee
, depth
);
3421 inline_edge_summary (e
)->loop_depth
+= depth
;
3423 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3424 inline_edge_summary (e
)->loop_depth
+= depth
;
3427 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3428 When functoin A is inlined in B and A calls C with parameter that
3429 changes with probability PROB1 and C is known to be passthroug
3430 of argument if B that change with probability PROB2, the probability
3431 of change is now PROB1*PROB2. */
3434 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3435 struct cgraph_edge
*edge
)
3437 if (ipa_node_params_sum
)
3440 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3441 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3442 struct inline_edge_summary
*inlined_es
3443 = inline_edge_summary (inlined_edge
);
3445 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3447 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3448 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3449 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3450 < (int) inlined_es
->param
.length ()))
3452 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3453 int prob1
= es
->param
[i
].change_prob
;
3454 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3455 int prob
= combine_probabilities (prob1
, prob2
);
3457 if (prob1
&& prob2
&& !prob
)
3460 es
->param
[i
].change_prob
= prob
;
3466 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3468 Remap predicates of callees of NODE. Rest of arguments match
3471 Also update change probabilities. */
3474 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3475 struct cgraph_node
*node
,
3476 struct inline_summary
*info
,
3477 struct inline_summary
*callee_info
,
3478 vec
<int> operand_map
,
3479 vec
<int> offset_map
,
3480 clause_t possible_truths
,
3481 struct predicate
*toplev_predicate
)
3483 struct cgraph_edge
*e
, *next
;
3484 for (e
= node
->callees
; e
; e
= next
)
3486 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3488 next
= e
->next_callee
;
3490 if (e
->inline_failed
)
3492 remap_edge_change_prob (inlined_edge
, e
);
3496 p
= remap_predicate (info
, callee_info
,
3497 es
->predicate
, operand_map
, offset_map
,
3498 possible_truths
, toplev_predicate
);
3499 edge_set_predicate (e
, &p
);
3502 edge_set_predicate (e
, toplev_predicate
);
3505 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3506 operand_map
, offset_map
, possible_truths
,
3509 for (e
= node
->indirect_calls
; e
; e
= next
)
3511 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3513 next
= e
->next_callee
;
3515 remap_edge_change_prob (inlined_edge
, e
);
3518 p
= remap_predicate (info
, callee_info
,
3519 es
->predicate
, operand_map
, offset_map
,
3520 possible_truths
, toplev_predicate
);
3521 edge_set_predicate (e
, &p
);
3524 edge_set_predicate (e
, toplev_predicate
);
3528 /* Same as remap_predicate, but set result into hint *HINT. */
3531 remap_hint_predicate (struct inline_summary
*info
,
3532 struct inline_summary
*callee_info
,
3533 struct predicate
**hint
,
3534 vec
<int> operand_map
,
3535 vec
<int> offset_map
,
3536 clause_t possible_truths
,
3537 struct predicate
*toplev_predicate
)
3543 p
= remap_predicate (info
, callee_info
,
3545 operand_map
, offset_map
,
3546 possible_truths
, toplev_predicate
);
3547 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3550 set_hint_predicate (hint
, p
);
3552 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3556 /* We inlined EDGE. Update summary of the function we inlined into. */
3559 inline_merge_summary (struct cgraph_edge
*edge
)
3561 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3562 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3563 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3564 struct inline_summary
*info
= inline_summaries
->get (to
);
3565 clause_t clause
= 0; /* not_inline is known to be false. */
3567 vec
<int> operand_map
= vNULL
;
3568 vec
<int> offset_map
= vNULL
;
3570 struct predicate toplev_predicate
;
3571 struct predicate true_p
= true_predicate ();
3572 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3575 toplev_predicate
= *es
->predicate
;
3577 toplev_predicate
= true_predicate ();
3579 if (callee_info
->conds
)
3580 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3581 if (ipa_node_params_sum
&& callee_info
->conds
)
3583 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3584 int count
= ipa_get_cs_argument_count (args
);
3589 operand_map
.safe_grow_cleared (count
);
3590 offset_map
.safe_grow_cleared (count
);
3592 for (i
= 0; i
< count
; i
++)
3594 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3597 /* TODO: handle non-NOPs when merging. */
3598 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3600 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3601 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3602 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3605 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3607 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3608 if (offset
>= 0 && offset
< INT_MAX
)
3610 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3611 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3613 offset_map
[i
] = offset
;
3616 operand_map
[i
] = map
;
3617 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3620 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3622 struct predicate p
= remap_predicate (info
, callee_info
,
3623 &e
->predicate
, operand_map
,
3626 if (!false_predicate_p (&p
))
3628 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3629 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3630 int prob
= predicate_probability (callee_info
->conds
,
3633 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3634 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3635 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3636 if (prob
!= REG_BR_PROB_BASE
3637 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3639 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3640 (double) prob
/ REG_BR_PROB_BASE
);
3642 account_size_time (info
, e
->size
, add_time
, &p
);
3645 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3646 offset_map
, clause
, &toplev_predicate
);
3647 remap_hint_predicate (info
, callee_info
,
3648 &callee_info
->loop_iterations
,
3649 operand_map
, offset_map
, clause
, &toplev_predicate
);
3650 remap_hint_predicate (info
, callee_info
,
3651 &callee_info
->loop_stride
,
3652 operand_map
, offset_map
, clause
, &toplev_predicate
);
3653 remap_hint_predicate (info
, callee_info
,
3654 &callee_info
->array_index
,
3655 operand_map
, offset_map
, clause
, &toplev_predicate
);
3657 inline_update_callee_summaries (edge
->callee
,
3658 inline_edge_summary (edge
)->loop_depth
);
3660 /* We do not maintain predicates of inlined edges, free it. */
3661 edge_set_predicate (edge
, &true_p
);
3662 /* Similarly remove param summaries. */
3663 es
->param
.release ();
3664 operand_map
.release ();
3665 offset_map
.release ();
3668 /* For performance reasons inline_merge_summary is not updating overall size
3669 and time. Recompute it. */
3672 inline_update_overall_summary (struct cgraph_node
*node
)
3674 struct inline_summary
*info
= inline_summaries
->get (node
);
3680 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3682 info
->size
+= e
->size
, info
->time
+= e
->time
;
3683 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3684 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3686 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3688 ~(clause_t
) (1 << predicate_false_condition
),
3689 vNULL
, vNULL
, vNULL
);
3690 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3691 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3694 /* Return hints derrived from EDGE. */
3696 simple_edge_hints (struct cgraph_edge
*edge
)
3699 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3700 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3701 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
3702 if (inline_summaries
->get (to
)->scc_no
3703 && inline_summaries
->get (to
)->scc_no
3704 == inline_summaries
->get (callee
)->scc_no
3705 && !edge
->recursive_p ())
3706 hints
|= INLINE_HINT_same_scc
;
3708 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
3709 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
3711 hints
|= INLINE_HINT_cross_module
;
3716 /* Estimate the time cost for the caller when inlining EDGE.
3717 Only to be called via estimate_edge_time, that handles the
3720 When caching, also update the cache entry. Compute both time and
3721 size, since we always need both metrics eventually. */
3724 do_estimate_edge_time (struct cgraph_edge
*edge
)
3729 struct cgraph_node
*callee
;
3731 vec
<tree
> known_vals
;
3732 vec
<ipa_polymorphic_call_context
> known_contexts
;
3733 vec
<ipa_agg_jump_function_p
> known_aggs
;
3734 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3737 callee
= edge
->callee
->ultimate_alias_target ();
3739 gcc_checking_assert (edge
->inline_failed
);
3740 evaluate_properties_for_edge (edge
, true,
3741 &clause
, &known_vals
, &known_contexts
,
3743 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3744 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3746 /* When we have profile feedback, we can quite safely identify hot
3747 edges and for those we disable size limits. Don't do that when
3748 probability that caller will call the callee is low however, since it
3749 may hurt optimization of the caller's hot path. */
3750 if (edge
->count
&& edge
->maybe_hot_p ()
3752 > (edge
->caller
->global
.inlined_to
3753 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3754 hints
|= INLINE_HINT_known_hot
;
3756 known_vals
.release ();
3757 known_contexts
.release ();
3758 known_aggs
.release ();
3759 gcc_checking_assert (size
>= 0);
3760 gcc_checking_assert (time
>= 0);
3762 /* When caching, update the cache entry. */
3763 if (edge_growth_cache
.exists ())
3765 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3766 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3767 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3768 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3770 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3771 hints
|= simple_edge_hints (edge
);
3772 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3778 /* Return estimated callee growth after inlining EDGE.
3779 Only to be called via estimate_edge_size. */
3782 do_estimate_edge_size (struct cgraph_edge
*edge
)
3785 struct cgraph_node
*callee
;
3787 vec
<tree
> known_vals
;
3788 vec
<ipa_polymorphic_call_context
> known_contexts
;
3789 vec
<ipa_agg_jump_function_p
> known_aggs
;
3791 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3793 if (edge_growth_cache
.exists ())
3795 do_estimate_edge_time (edge
);
3796 size
= edge_growth_cache
[edge
->uid
].size
;
3797 gcc_checking_assert (size
);
3798 return size
- (size
> 0);
3801 callee
= edge
->callee
->ultimate_alias_target ();
3803 /* Early inliner runs without caching, go ahead and do the dirty work. */
3804 gcc_checking_assert (edge
->inline_failed
);
3805 evaluate_properties_for_edge (edge
, true,
3806 &clause
, &known_vals
, &known_contexts
,
3808 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3809 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3810 known_vals
.release ();
3811 known_contexts
.release ();
3812 known_aggs
.release ();
3817 /* Estimate the growth of the caller when inlining EDGE.
3818 Only to be called via estimate_edge_size. */
3821 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3824 struct cgraph_node
*callee
;
3826 vec
<tree
> known_vals
;
3827 vec
<ipa_polymorphic_call_context
> known_contexts
;
3828 vec
<ipa_agg_jump_function_p
> known_aggs
;
3830 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3832 if (edge_growth_cache
.exists ())
3834 do_estimate_edge_time (edge
);
3835 hints
= edge_growth_cache
[edge
->uid
].hints
;
3836 gcc_checking_assert (hints
);
3840 callee
= edge
->callee
->ultimate_alias_target ();
3842 /* Early inliner runs without caching, go ahead and do the dirty work. */
3843 gcc_checking_assert (edge
->inline_failed
);
3844 evaluate_properties_for_edge (edge
, true,
3845 &clause
, &known_vals
, &known_contexts
,
3847 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3848 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3849 known_vals
.release ();
3850 known_contexts
.release ();
3851 known_aggs
.release ();
3852 hints
|= simple_edge_hints (edge
);
3857 /* Estimate self time of the function NODE after inlining EDGE. */
3860 estimate_time_after_inlining (struct cgraph_node
*node
,
3861 struct cgraph_edge
*edge
)
3863 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3864 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3867 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3870 if (time
> MAX_TIME
)
3874 return inline_summaries
->get (node
)->time
;
3878 /* Estimate the size of NODE after inlining EDGE which should be an
3879 edge to either NODE or a call inlined into NODE. */
3882 estimate_size_after_inlining (struct cgraph_node
*node
,
3883 struct cgraph_edge
*edge
)
3885 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3886 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3888 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3889 gcc_assert (size
>= 0);
3892 return inline_summaries
->get (node
)->size
;
3898 struct cgraph_node
*node
;
3899 bool self_recursive
;
3905 /* Worker for do_estimate_growth. Collect growth for all callers. */
3908 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3910 struct cgraph_edge
*e
;
3911 struct growth_data
*d
= (struct growth_data
*) data
;
3913 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3915 gcc_checking_assert (e
->inline_failed
);
3917 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3919 d
->uninlinable
= true;
3923 if (e
->recursive_p ())
3925 d
->self_recursive
= true;
3928 d
->growth
+= estimate_edge_growth (e
);
3934 /* Estimate the growth caused by inlining NODE into all callees. */
3937 estimate_growth (struct cgraph_node
*node
)
3939 struct growth_data d
= { node
, false, false, 0 };
3940 struct inline_summary
*info
= inline_summaries
->get (node
);
3942 node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true);
3944 /* For self recursive functions the growth estimation really should be
3945 infinity. We don't want to return very large values because the growth
3946 plays various roles in badness computation fractions. Be sure to not
3947 return zero or negative growths. */
3948 if (d
.self_recursive
)
3949 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3950 else if (DECL_EXTERNAL (node
->decl
) || d
.uninlinable
)
3954 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3955 d
.growth
-= info
->size
;
3956 /* COMDAT functions are very often not shared across multiple units
3957 since they come from various template instantiations.
3958 Take this into account. */
3959 else if (DECL_COMDAT (node
->decl
)
3960 && node
->can_remove_if_no_direct_calls_p ())
3961 d
.growth
-= (info
->size
3962 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3969 /* Verify if there are fewer than MAX_CALLERS. */
3972 check_callers (cgraph_node
*node
, int *max_callers
)
3976 if (!node
->can_remove_if_no_direct_calls_and_refs_p ())
3979 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
3983 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3987 FOR_EACH_ALIAS (node
, ref
)
3988 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), max_callers
))
3995 /* Make cheap estimation if growth of NODE is likely positive knowing
3996 EDGE_GROWTH of one particular edge.
3997 We assume that most of other edges will have similar growth
3998 and skip computation if there are too many callers. */
4001 growth_likely_positive (struct cgraph_node
*node
,
4005 struct cgraph_edge
*e
;
4006 gcc_checking_assert (edge_growth
> 0);
4008 /* First quickly check if NODE is removable at all. */
4009 if (DECL_EXTERNAL (node
->decl
))
4011 if (!node
->can_remove_if_no_direct_calls_and_refs_p ()
4012 || node
->address_taken
)
4015 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
4017 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4021 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4026 FOR_EACH_ALIAS (node
, ref
)
4027 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), &max_callers
))
4030 /* Unlike for functions called once, we play unsafe with
4031 COMDATs. We can allow that since we know functions
4032 in consideration are small (and thus risk is small) and
4033 moreover grow estimates already accounts that COMDAT
4034 functions may or may not disappear when eliminated from
4035 current unit. With good probability making aggressive
4036 choice in all units is going to make overall program
4038 if (DECL_COMDAT (node
->decl
))
4040 if (!node
->can_remove_if_no_direct_calls_p ())
4043 else if (!node
->will_be_removed_from_program_if_no_direct_calls_p ())
4046 return estimate_growth (node
) > 0;
4050 /* This function performs intraprocedural analysis in NODE that is required to
4051 inline indirect calls. */
4054 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4056 ipa_analyze_node (node
);
4057 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4059 ipa_print_node_params (dump_file
, node
);
4060 ipa_print_node_jump_functions (dump_file
, node
);
4065 /* Note function body size. */
4068 inline_analyze_function (struct cgraph_node
*node
)
4070 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4073 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4074 node
->name (), node
->order
);
4075 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4076 inline_indirect_intraprocedural_analysis (node
);
4077 compute_inline_parameters (node
, false);
4080 struct cgraph_edge
*e
;
4081 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4083 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4084 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4085 e
->call_stmt_cannot_inline_p
= true;
4087 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4089 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4090 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4091 e
->call_stmt_cannot_inline_p
= true;
4099 /* Called when new function is inserted to callgraph late. */
4102 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4104 inline_analyze_function (node
);
4107 /* Note function body size. */
4110 inline_generate_summary (void)
4112 struct cgraph_node
*node
;
4114 /* When not optimizing, do not bother to analyze. Inlining is still done
4115 because edge redirection needs to happen there. */
4116 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4119 if (!inline_summaries
)
4120 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4122 inline_summaries
->enable_insertion_hook ();
4124 ipa_register_cgraph_hooks ();
4125 inline_free_summary ();
4127 FOR_EACH_DEFINED_FUNCTION (node
)
4129 inline_analyze_function (node
);
4133 /* Read predicate from IB. */
4135 static struct predicate
4136 read_predicate (struct lto_input_block
*ib
)
4138 struct predicate out
;
4144 gcc_assert (k
<= MAX_CLAUSES
);
4145 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4149 /* Zero-initialize the remaining clauses in OUT. */
4150 while (k
<= MAX_CLAUSES
)
4151 out
.clause
[k
++] = 0;
4157 /* Write inline summary for edge E to OB. */
4160 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4162 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4166 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4167 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4168 es
->loop_depth
= streamer_read_uhwi (ib
);
4169 p
= read_predicate (ib
);
4170 edge_set_predicate (e
, &p
);
4171 length
= streamer_read_uhwi (ib
);
4174 es
->param
.safe_grow_cleared (length
);
4175 for (i
= 0; i
< length
; i
++)
4176 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4181 /* Stream in inline summaries from the section. */
4184 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4187 const struct lto_function_header
*header
=
4188 (const struct lto_function_header
*) data
;
4189 const int cfg_offset
= sizeof (struct lto_function_header
);
4190 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4191 const int string_offset
= main_offset
+ header
->main_size
;
4192 struct data_in
*data_in
;
4193 unsigned int i
, count2
, j
;
4194 unsigned int f_count
;
4196 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
,
4197 file_data
->mode_table
);
4200 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4201 header
->string_size
, vNULL
);
4202 f_count
= streamer_read_uhwi (&ib
);
4203 for (i
= 0; i
< f_count
; i
++)
4206 struct cgraph_node
*node
;
4207 struct inline_summary
*info
;
4208 lto_symtab_encoder_t encoder
;
4209 struct bitpack_d bp
;
4210 struct cgraph_edge
*e
;
4213 index
= streamer_read_uhwi (&ib
);
4214 encoder
= file_data
->symtab_node_encoder
;
4215 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4217 info
= inline_summaries
->get (node
);
4219 info
->estimated_stack_size
4220 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4221 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4222 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4224 bp
= streamer_read_bitpack (&ib
);
4225 info
->inlinable
= bp_unpack_value (&bp
, 1);
4226 info
->contains_cilk_spawn
= bp_unpack_value (&bp
, 1);
4228 count2
= streamer_read_uhwi (&ib
);
4229 gcc_assert (!info
->conds
);
4230 for (j
= 0; j
< count2
; j
++)
4233 c
.operand_num
= streamer_read_uhwi (&ib
);
4234 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4235 c
.val
= stream_read_tree (&ib
, data_in
);
4236 bp
= streamer_read_bitpack (&ib
);
4237 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4238 c
.by_ref
= bp_unpack_value (&bp
, 1);
4240 c
.offset
= streamer_read_uhwi (&ib
);
4241 vec_safe_push (info
->conds
, c
);
4243 count2
= streamer_read_uhwi (&ib
);
4244 gcc_assert (!info
->entry
);
4245 for (j
= 0; j
< count2
; j
++)
4247 struct size_time_entry e
;
4249 e
.size
= streamer_read_uhwi (&ib
);
4250 e
.time
= streamer_read_uhwi (&ib
);
4251 e
.predicate
= read_predicate (&ib
);
4253 vec_safe_push (info
->entry
, e
);
4256 p
= read_predicate (&ib
);
4257 set_hint_predicate (&info
->loop_iterations
, p
);
4258 p
= read_predicate (&ib
);
4259 set_hint_predicate (&info
->loop_stride
, p
);
4260 p
= read_predicate (&ib
);
4261 set_hint_predicate (&info
->array_index
, p
);
4262 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4263 read_inline_edge_summary (&ib
, e
);
4264 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4265 read_inline_edge_summary (&ib
, e
);
4268 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4270 lto_data_in_delete (data_in
);
4274 /* Read inline summary. Jump functions are shared among ipa-cp
4275 and inliner, so when ipa-cp is active, we don't need to write them
4279 inline_read_summary (void)
4281 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4282 struct lto_file_decl_data
*file_data
;
4285 inline_summary_alloc ();
4287 while ((file_data
= file_data_vec
[j
++]))
4290 const char *data
= lto_get_section_data (file_data
,
4291 LTO_section_inline_summary
,
4294 inline_read_section (file_data
, data
, len
);
4296 /* Fatal error here. We do not want to support compiling ltrans units
4297 with different version of compiler or different flags than the WPA
4298 unit, so this should never happen. */
4299 fatal_error (input_location
,
4300 "ipa inline summary is missing in input file");
4304 ipa_register_cgraph_hooks ();
4306 ipa_prop_read_jump_functions ();
4309 gcc_assert (inline_summaries
);
4310 inline_summaries
->enable_insertion_hook ();
4314 /* Write predicate P to OB. */
4317 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4321 for (j
= 0; p
->clause
[j
]; j
++)
4323 gcc_assert (j
< MAX_CLAUSES
);
4324 streamer_write_uhwi (ob
, p
->clause
[j
]);
4326 streamer_write_uhwi (ob
, 0);
4330 /* Write inline summary for edge E to OB. */
4333 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4335 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4338 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4339 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4340 streamer_write_uhwi (ob
, es
->loop_depth
);
4341 write_predicate (ob
, es
->predicate
);
4342 streamer_write_uhwi (ob
, es
->param
.length ());
4343 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4344 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4348 /* Write inline summary for node in SET.
4349 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4350 active, we don't need to write them twice. */
4353 inline_write_summary (void)
4355 struct cgraph_node
*node
;
4356 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4357 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4358 unsigned int count
= 0;
4361 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4363 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4364 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4365 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4368 streamer_write_uhwi (ob
, count
);
4370 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4372 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4373 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4374 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4376 struct inline_summary
*info
= inline_summaries
->get (node
);
4377 struct bitpack_d bp
;
4378 struct cgraph_edge
*edge
;
4381 struct condition
*c
;
4383 streamer_write_uhwi (ob
,
4384 lto_symtab_encoder_encode (encoder
,
4387 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4388 streamer_write_hwi (ob
, info
->self_size
);
4389 streamer_write_hwi (ob
, info
->self_time
);
4390 bp
= bitpack_create (ob
->main_stream
);
4391 bp_pack_value (&bp
, info
->inlinable
, 1);
4392 bp_pack_value (&bp
, info
->contains_cilk_spawn
, 1);
4393 streamer_write_bitpack (&bp
);
4394 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4395 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4397 streamer_write_uhwi (ob
, c
->operand_num
);
4398 streamer_write_uhwi (ob
, c
->code
);
4399 stream_write_tree (ob
, c
->val
, true);
4400 bp
= bitpack_create (ob
->main_stream
);
4401 bp_pack_value (&bp
, c
->agg_contents
, 1);
4402 bp_pack_value (&bp
, c
->by_ref
, 1);
4403 streamer_write_bitpack (&bp
);
4404 if (c
->agg_contents
)
4405 streamer_write_uhwi (ob
, c
->offset
);
4407 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4408 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4410 streamer_write_uhwi (ob
, e
->size
);
4411 streamer_write_uhwi (ob
, e
->time
);
4412 write_predicate (ob
, &e
->predicate
);
4414 write_predicate (ob
, info
->loop_iterations
);
4415 write_predicate (ob
, info
->loop_stride
);
4416 write_predicate (ob
, info
->array_index
);
4417 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4418 write_inline_edge_summary (ob
, edge
);
4419 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4420 write_inline_edge_summary (ob
, edge
);
4423 streamer_write_char_stream (ob
->main_stream
, 0);
4424 produce_asm (ob
, NULL
);
4425 destroy_output_block (ob
);
4427 if (optimize
&& !flag_ipa_cp
)
4428 ipa_prop_write_jump_functions ();
4432 /* Release inline summary. */
4435 inline_free_summary (void)
4437 struct cgraph_node
*node
;
4438 if (edge_removal_hook_holder
)
4439 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4440 edge_removal_hook_holder
= NULL
;
4441 if (edge_duplication_hook_holder
)
4442 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4443 edge_duplication_hook_holder
= NULL
;
4444 if (!inline_edge_summary_vec
.exists ())
4446 FOR_EACH_DEFINED_FUNCTION (node
)
4448 reset_inline_summary (node
, inline_summaries
->get (node
));
4449 inline_summaries
->release ();
4450 inline_summaries
= NULL
;
4451 inline_edge_summary_vec
.release ();
4452 edge_predicate_pool
.release ();