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"
73 #include "alloc-pool.h"
74 #include "tree-pass.h"
76 #include "tree-streamer.h"
78 #include "diagnostic.h"
79 #include "fold-const.h"
80 #include "print-tree.h"
81 #include "tree-inline.h"
82 #include "gimple-pretty-print.h"
85 #include "gimple-iterator.h"
87 #include "tree-ssa-loop-niter.h"
88 #include "tree-ssa-loop.h"
89 #include "symbol-summary.h"
91 #include "ipa-inline.h"
93 #include "tree-scalar-evolution.h"
94 #include "ipa-utils.h"
96 #include "cfgexpand.h"
98 /* Estimate runtime of function can easilly run into huge numbers with many
99 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
100 integer. For anything larger we use gcov_type. */
101 #define MAX_TIME 500000
103 /* Number of bits in integer, but we really want to be stable across different
105 #define NUM_CONDITIONS 32
107 enum predicate_conditions
109 predicate_false_condition
= 0,
110 predicate_not_inlined_condition
= 1,
111 predicate_first_dynamic_condition
= 2
114 /* Special condition code we use to represent test that operand is compile time
116 #define IS_NOT_CONSTANT ERROR_MARK
117 /* Special condition code we use to represent test that operand is not changed
118 across invocation of the function. When operand IS_NOT_CONSTANT it is always
119 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
120 of executions even when they are not compile time constants. */
121 #define CHANGED IDENTIFIER_NODE
123 /* Holders of ipa cgraph hooks: */
124 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
125 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
126 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
127 static void inline_edge_duplication_hook (struct cgraph_edge
*,
128 struct cgraph_edge
*, void *);
130 /* VECtor holding inline summaries.
131 In GGC memory because conditions might point to constant trees. */
132 function_summary
<inline_summary
*> *inline_summaries
;
133 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
135 /* Cached node/edge growths. */
136 vec
<edge_growth_cache_entry
> edge_growth_cache
;
138 /* Edge predicates goes here. */
139 static object_allocator
<predicate
> edge_predicate_pool ("edge predicates");
141 /* Return true predicate (tautology).
142 We represent it by empty list of clauses. */
144 static inline struct predicate
145 true_predicate (void)
153 /* Return predicate testing single condition number COND. */
155 static inline struct predicate
156 single_cond_predicate (int cond
)
159 p
.clause
[0] = 1 << cond
;
165 /* Return false predicate. First clause require false condition. */
167 static inline struct predicate
168 false_predicate (void)
170 return single_cond_predicate (predicate_false_condition
);
174 /* Return true if P is (true). */
177 true_predicate_p (struct predicate
*p
)
179 return !p
->clause
[0];
183 /* Return true if P is (false). */
186 false_predicate_p (struct predicate
*p
)
188 if (p
->clause
[0] == (1 << predicate_false_condition
))
190 gcc_checking_assert (!p
->clause
[1]
191 && p
->clause
[0] == 1 << predicate_false_condition
);
198 /* Return predicate that is set true when function is not inlined. */
200 static inline struct predicate
201 not_inlined_predicate (void)
203 return single_cond_predicate (predicate_not_inlined_condition
);
206 /* Simple description of whether a memory load or a condition refers to a load
207 from an aggregate and if so, how and where from in the aggregate.
208 Individual fields have the same meaning like fields with the same name in
211 struct agg_position_info
213 HOST_WIDE_INT offset
;
218 /* Add condition to condition list CONDS. AGGPOS describes whether the used
219 oprand is loaded from an aggregate and where in the aggregate it is. It can
220 be NULL, which means this not a load from an aggregate. */
222 static struct predicate
223 add_condition (struct inline_summary
*summary
, int operand_num
,
224 struct agg_position_info
*aggpos
,
225 enum tree_code code
, tree val
)
229 struct condition new_cond
;
230 HOST_WIDE_INT offset
;
231 bool agg_contents
, by_ref
;
235 offset
= aggpos
->offset
;
236 agg_contents
= aggpos
->agg_contents
;
237 by_ref
= aggpos
->by_ref
;
242 agg_contents
= false;
246 gcc_checking_assert (operand_num
>= 0);
247 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
249 if (c
->operand_num
== operand_num
252 && c
->agg_contents
== agg_contents
253 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
254 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
256 /* Too many conditions. Give up and return constant true. */
257 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
258 return true_predicate ();
260 new_cond
.operand_num
= operand_num
;
261 new_cond
.code
= code
;
263 new_cond
.agg_contents
= agg_contents
;
264 new_cond
.by_ref
= by_ref
;
265 new_cond
.offset
= offset
;
266 vec_safe_push (summary
->conds
, new_cond
);
267 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
271 /* Add clause CLAUSE into the predicate P. */
274 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
278 int insert_here
= -1;
285 /* False clause makes the whole predicate false. Kill the other variants. */
286 if (clause
== (1 << predicate_false_condition
))
288 p
->clause
[0] = (1 << predicate_false_condition
);
292 if (false_predicate_p (p
))
295 /* No one should be silly enough to add false into nontrivial clauses. */
296 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
298 /* Look where to insert the clause. At the same time prune out
299 clauses of P that are implied by the new clause and thus
301 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
303 p
->clause
[i2
] = p
->clause
[i
];
308 /* If p->clause[i] implies clause, there is nothing to add. */
309 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
311 /* We had nothing to add, none of clauses should've become
313 gcc_checking_assert (i
== i2
);
317 if (p
->clause
[i
] < clause
&& insert_here
< 0)
320 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
321 Otherwise the p->clause[i] has to stay. */
322 if ((p
->clause
[i
] & clause
) != clause
)
326 /* Look for clauses that are obviously true. I.e.
327 op0 == 5 || op0 != 5. */
328 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
331 if (!(clause
& (1 << c1
)))
333 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
334 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
335 and thus there is no point for looking for them. */
336 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
338 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
339 if (clause
& (1 << c2
))
342 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
344 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
345 if (cc1
->operand_num
== cc2
->operand_num
346 && cc1
->val
== cc2
->val
347 && cc2
->code
!= IS_NOT_CONSTANT
348 && cc2
->code
!= CHANGED
349 && cc1
->code
== invert_tree_comparison (cc2
->code
,
350 HONOR_NANS (cc1
->val
)))
356 /* We run out of variants. Be conservative in positive direction. */
357 if (i2
== MAX_CLAUSES
)
359 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
360 p
->clause
[i2
+ 1] = 0;
361 if (insert_here
>= 0)
362 for (; i2
> insert_here
; i2
--)
363 p
->clause
[i2
] = p
->clause
[i2
- 1];
366 p
->clause
[insert_here
] = clause
;
372 static struct predicate
373 and_predicates (conditions conditions
,
374 struct predicate
*p
, struct predicate
*p2
)
376 struct predicate out
= *p
;
379 /* Avoid busy work. */
380 if (false_predicate_p (p2
) || true_predicate_p (p
))
382 if (false_predicate_p (p
) || true_predicate_p (p2
))
385 /* See how far predicates match. */
386 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
388 gcc_checking_assert (i
< MAX_CLAUSES
);
391 /* Combine the predicates rest. */
392 for (; p2
->clause
[i
]; i
++)
394 gcc_checking_assert (i
< MAX_CLAUSES
);
395 add_clause (conditions
, &out
, p2
->clause
[i
]);
401 /* Return true if predicates are obviously equal. */
404 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
407 for (i
= 0; p
->clause
[i
]; i
++)
409 gcc_checking_assert (i
< MAX_CLAUSES
);
410 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
411 gcc_checking_assert (!p2
->clause
[i
]
412 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
413 if (p
->clause
[i
] != p2
->clause
[i
])
416 return !p2
->clause
[i
];
422 static struct predicate
423 or_predicates (conditions conditions
,
424 struct predicate
*p
, struct predicate
*p2
)
426 struct predicate out
= true_predicate ();
429 /* Avoid busy work. */
430 if (false_predicate_p (p2
) || true_predicate_p (p
))
432 if (false_predicate_p (p
) || true_predicate_p (p2
))
434 if (predicates_equal_p (p
, p2
))
437 /* OK, combine the predicates. */
438 for (i
= 0; p
->clause
[i
]; i
++)
439 for (j
= 0; p2
->clause
[j
]; j
++)
441 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
442 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
448 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
449 if predicate P is known to be false. */
452 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
456 /* True remains true. */
457 if (true_predicate_p (p
))
460 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
462 /* See if we can find clause we can disprove. */
463 for (i
= 0; p
->clause
[i
]; i
++)
465 gcc_checking_assert (i
< MAX_CLAUSES
);
466 if (!(p
->clause
[i
] & possible_truths
))
472 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
473 instruction will be recomputed per invocation of the inlined call. */
476 predicate_probability (conditions conds
,
477 struct predicate
*p
, clause_t possible_truths
,
478 vec
<inline_param_summary
> inline_param_summary
)
481 int combined_prob
= REG_BR_PROB_BASE
;
483 /* True remains true. */
484 if (true_predicate_p (p
))
485 return REG_BR_PROB_BASE
;
487 if (false_predicate_p (p
))
490 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
492 /* See if we can find clause we can disprove. */
493 for (i
= 0; p
->clause
[i
]; i
++)
495 gcc_checking_assert (i
< MAX_CLAUSES
);
496 if (!(p
->clause
[i
] & possible_truths
))
502 if (!inline_param_summary
.exists ())
503 return REG_BR_PROB_BASE
;
504 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
505 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
507 if (i2
>= predicate_first_dynamic_condition
)
510 &(*conds
)[i2
- predicate_first_dynamic_condition
];
511 if (c
->code
== CHANGED
513 (int) inline_param_summary
.length ()))
516 inline_param_summary
[c
->operand_num
].change_prob
;
517 this_prob
= MAX (this_prob
, iprob
);
520 this_prob
= REG_BR_PROB_BASE
;
523 this_prob
= REG_BR_PROB_BASE
;
525 combined_prob
= MIN (this_prob
, combined_prob
);
530 return combined_prob
;
534 /* Dump conditional COND. */
537 dump_condition (FILE *f
, conditions conditions
, int cond
)
540 if (cond
== predicate_false_condition
)
541 fprintf (f
, "false");
542 else if (cond
== predicate_not_inlined_condition
)
543 fprintf (f
, "not inlined");
546 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
547 fprintf (f
, "op%i", c
->operand_num
);
549 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
550 c
->by_ref
? "ref " : "", c
->offset
);
551 if (c
->code
== IS_NOT_CONSTANT
)
553 fprintf (f
, " not constant");
556 if (c
->code
== CHANGED
)
558 fprintf (f
, " changed");
561 fprintf (f
, " %s ", op_symbol_code (c
->code
));
562 print_generic_expr (f
, c
->val
, 1);
567 /* Dump clause CLAUSE. */
570 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
577 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
578 if (clause
& (1 << i
))
583 dump_condition (f
, conds
, i
);
589 /* Dump predicate PREDICATE. */
592 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
595 if (true_predicate_p (pred
))
596 dump_clause (f
, conds
, 0);
598 for (i
= 0; pred
->clause
[i
]; i
++)
602 dump_clause (f
, conds
, pred
->clause
[i
]);
608 /* Dump inline hints. */
610 dump_inline_hints (FILE *f
, inline_hints hints
)
614 fprintf (f
, "inline hints:");
615 if (hints
& INLINE_HINT_indirect_call
)
617 hints
&= ~INLINE_HINT_indirect_call
;
618 fprintf (f
, " indirect_call");
620 if (hints
& INLINE_HINT_loop_iterations
)
622 hints
&= ~INLINE_HINT_loop_iterations
;
623 fprintf (f
, " loop_iterations");
625 if (hints
& INLINE_HINT_loop_stride
)
627 hints
&= ~INLINE_HINT_loop_stride
;
628 fprintf (f
, " loop_stride");
630 if (hints
& INLINE_HINT_same_scc
)
632 hints
&= ~INLINE_HINT_same_scc
;
633 fprintf (f
, " same_scc");
635 if (hints
& INLINE_HINT_in_scc
)
637 hints
&= ~INLINE_HINT_in_scc
;
638 fprintf (f
, " in_scc");
640 if (hints
& INLINE_HINT_cross_module
)
642 hints
&= ~INLINE_HINT_cross_module
;
643 fprintf (f
, " cross_module");
645 if (hints
& INLINE_HINT_declared_inline
)
647 hints
&= ~INLINE_HINT_declared_inline
;
648 fprintf (f
, " declared_inline");
650 if (hints
& INLINE_HINT_array_index
)
652 hints
&= ~INLINE_HINT_array_index
;
653 fprintf (f
, " array_index");
655 if (hints
& INLINE_HINT_known_hot
)
657 hints
&= ~INLINE_HINT_known_hot
;
658 fprintf (f
, " known_hot");
664 /* Record SIZE and TIME under condition PRED into the inline summary. */
667 account_size_time (struct inline_summary
*summary
, int size
, int time
,
668 struct predicate
*pred
)
674 if (false_predicate_p (pred
))
677 /* We need to create initial empty unconitional clause, but otherwie
678 we don't need to account empty times and sizes. */
679 if (!size
&& !time
&& summary
->entry
)
682 /* Watch overflow that might result from insane profiles. */
683 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
684 time
= MAX_TIME
* INLINE_TIME_SCALE
;
685 gcc_assert (time
>= 0);
687 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
688 if (predicates_equal_p (&e
->predicate
, pred
))
697 e
= &(*summary
->entry
)[0];
698 gcc_assert (!e
->predicate
.clause
[0]);
699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
701 "\t\tReached limit on number of entries, "
702 "ignoring the predicate.");
704 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
707 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
708 ((double) size
) / INLINE_SIZE_SCALE
,
709 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
710 dump_predicate (dump_file
, summary
->conds
, pred
);
714 struct size_time_entry new_entry
;
715 new_entry
.size
= size
;
716 new_entry
.time
= time
;
717 new_entry
.predicate
= *pred
;
718 vec_safe_push (summary
->entry
, new_entry
);
724 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
725 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
729 /* We proved E to be unreachable, redirect it to __bultin_unreachable. */
731 static struct cgraph_edge
*
732 redirect_to_unreachable (struct cgraph_edge
*e
)
734 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
735 struct cgraph_node
*target
= cgraph_node::get_create
736 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
));
739 e
= e
->resolve_speculation (target
->decl
);
741 e
->make_direct (target
);
743 e
->redirect_callee (target
);
744 struct inline_edge_summary
*es
= inline_edge_summary (e
);
745 e
->inline_failed
= CIF_UNREACHABLE
;
748 es
->call_stmt_size
= 0;
749 es
->call_stmt_time
= 0;
751 callee
->remove_symbol_and_inline_clones ();
755 /* Set predicate for edge E. */
758 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
760 /* If the edge is determined to be never executed, redirect it
761 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
762 if (predicate
&& false_predicate_p (predicate
)
763 /* When handling speculative edges, we need to do the redirection
764 just once. Do it always on the direct edge, so we do not
765 attempt to resolve speculation while duplicating the edge. */
766 && (!e
->speculative
|| e
->callee
))
767 e
= redirect_to_unreachable (e
);
769 struct inline_edge_summary
*es
= inline_edge_summary (e
);
770 if (predicate
&& !true_predicate_p (predicate
))
773 es
->predicate
= edge_predicate_pool
.allocate ();
774 *es
->predicate
= *predicate
;
779 edge_predicate_pool
.remove (es
->predicate
);
780 es
->predicate
= NULL
;
784 /* Set predicate for hint *P. */
787 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
789 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
792 edge_predicate_pool
.remove (*p
);
798 *p
= edge_predicate_pool
.allocate ();
804 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
805 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
806 Return clause of possible truths. When INLINE_P is true, assume that we are
809 ERROR_MARK means compile time invariant. */
812 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
814 vec
<tree
> known_vals
,
815 vec
<ipa_agg_jump_function_p
>
818 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
819 struct inline_summary
*info
= inline_summaries
->get (node
);
823 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
828 /* We allow call stmt to have fewer arguments than the callee function
829 (especially for K&R style programs). So bound check here (we assume
830 known_aggs vector, if non-NULL, has the same length as
832 gcc_checking_assert (!known_aggs
.exists ()
833 || (known_vals
.length () == known_aggs
.length ()));
834 if (c
->operand_num
>= (int) known_vals
.length ())
836 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
842 struct ipa_agg_jump_function
*agg
;
844 if (c
->code
== CHANGED
846 && (known_vals
[c
->operand_num
] == error_mark_node
))
849 if (known_aggs
.exists ())
851 agg
= known_aggs
[c
->operand_num
];
852 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
859 val
= known_vals
[c
->operand_num
];
860 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
866 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
869 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
872 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
873 TYPE_SIZE (TREE_TYPE (val
)), 0))
875 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
878 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
881 if (res
&& integer_zerop (res
))
884 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
890 /* Work out what conditions might be true at invocation of E. */
893 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
894 clause_t
*clause_ptr
,
895 vec
<tree
> *known_vals_ptr
,
896 vec
<ipa_polymorphic_call_context
>
898 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
900 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
901 struct inline_summary
*info
= inline_summaries
->get (callee
);
902 vec
<tree
> known_vals
= vNULL
;
903 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
906 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
908 known_vals_ptr
->create (0);
909 if (known_contexts_ptr
)
910 known_contexts_ptr
->create (0);
912 if (ipa_node_params_sum
913 && !e
->call_stmt_cannot_inline_p
914 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
916 struct ipa_node_params
*parms_info
;
917 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
918 struct inline_edge_summary
*es
= inline_edge_summary (e
);
919 int i
, count
= ipa_get_cs_argument_count (args
);
921 if (e
->caller
->global
.inlined_to
)
922 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
924 parms_info
= IPA_NODE_REF (e
->caller
);
926 if (count
&& (info
->conds
|| known_vals_ptr
))
927 known_vals
.safe_grow_cleared (count
);
928 if (count
&& (info
->conds
|| known_aggs_ptr
))
929 known_aggs
.safe_grow_cleared (count
);
930 if (count
&& known_contexts_ptr
)
931 known_contexts_ptr
->safe_grow_cleared (count
);
933 for (i
= 0; i
< count
; i
++)
935 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
936 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
938 if (!cst
&& e
->call_stmt
939 && i
< (int)gimple_call_num_args (e
->call_stmt
))
941 cst
= gimple_call_arg (e
->call_stmt
, i
);
942 if (!is_gimple_min_invariant (cst
))
947 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
948 if (known_vals
.exists ())
951 else if (inline_p
&& !es
->param
[i
].change_prob
)
952 known_vals
[i
] = error_mark_node
;
954 if (known_contexts_ptr
)
955 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
957 /* TODO: When IPA-CP starts propagating and merging aggregate jump
958 functions, use its knowledge of the caller too, just like the
959 scalar case above. */
960 known_aggs
[i
] = &jf
->agg
;
963 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
964 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
966 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
968 if (count
&& (info
->conds
|| known_vals_ptr
))
969 known_vals
.safe_grow_cleared (count
);
970 for (i
= 0; i
< count
; i
++)
972 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
973 if (!is_gimple_min_invariant (cst
))
981 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
982 known_vals
, known_aggs
);
985 *known_vals_ptr
= known_vals
;
987 known_vals
.release ();
990 *known_aggs_ptr
= known_aggs
;
992 known_aggs
.release ();
996 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
999 inline_summary_alloc (void)
1001 if (!edge_removal_hook_holder
)
1002 edge_removal_hook_holder
=
1003 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1004 if (!edge_duplication_hook_holder
)
1005 edge_duplication_hook_holder
=
1006 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1008 if (!inline_summaries
)
1009 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1011 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1012 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1015 /* We are called multiple time for given function; clear
1016 data from previous run so they are not cumulated. */
1019 reset_inline_edge_summary (struct cgraph_edge
*e
)
1021 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1023 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1025 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1027 edge_predicate_pool
.remove (es
->predicate
);
1028 es
->predicate
= NULL
;
1029 es
->param
.release ();
1033 /* We are called multiple time for given function; clear
1034 data from previous run so they are not cumulated. */
1037 reset_inline_summary (struct cgraph_node
*node
,
1038 inline_summary
*info
)
1040 struct cgraph_edge
*e
;
1042 info
->self_size
= info
->self_time
= 0;
1043 info
->estimated_stack_size
= 0;
1044 info
->estimated_self_stack_size
= 0;
1045 info
->stack_frame_offset
= 0;
1050 if (info
->loop_iterations
)
1052 edge_predicate_pool
.remove (info
->loop_iterations
);
1053 info
->loop_iterations
= NULL
;
1055 if (info
->loop_stride
)
1057 edge_predicate_pool
.remove (info
->loop_stride
);
1058 info
->loop_stride
= NULL
;
1060 if (info
->array_index
)
1062 edge_predicate_pool
.remove (info
->array_index
);
1063 info
->array_index
= NULL
;
1065 vec_free (info
->conds
);
1066 vec_free (info
->entry
);
1067 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1068 reset_inline_edge_summary (e
);
1069 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1070 reset_inline_edge_summary (e
);
1073 /* Hook that is called by cgraph.c when a node is removed. */
1076 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1078 reset_inline_summary (node
, info
);
1081 /* Remap predicate P of former function to be predicate of duplicated function.
1082 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1083 INFO is inline summary of the duplicated node. */
1085 static struct predicate
1086 remap_predicate_after_duplication (struct predicate
*p
,
1087 clause_t possible_truths
,
1088 struct inline_summary
*info
)
1090 struct predicate new_predicate
= true_predicate ();
1092 for (j
= 0; p
->clause
[j
]; j
++)
1093 if (!(possible_truths
& p
->clause
[j
]))
1095 new_predicate
= false_predicate ();
1099 add_clause (info
->conds
, &new_predicate
,
1100 possible_truths
& p
->clause
[j
]);
1101 return new_predicate
;
1104 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1105 Additionally care about allocating new memory slot for updated predicate
1106 and set it to NULL when it becomes true or false (and thus uninteresting).
1110 remap_hint_predicate_after_duplication (struct predicate
**p
,
1111 clause_t possible_truths
,
1112 struct inline_summary
*info
)
1114 struct predicate new_predicate
;
1119 new_predicate
= remap_predicate_after_duplication (*p
,
1120 possible_truths
, info
);
1121 /* We do not want to free previous predicate; it is used by node origin. */
1123 set_hint_predicate (p
, new_predicate
);
1127 /* Hook that is called by cgraph.c when a node is duplicated. */
1129 inline_summary_t::duplicate (cgraph_node
*src
,
1132 inline_summary
*info
)
1134 inline_summary_alloc ();
1135 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1136 /* TODO: as an optimization, we may avoid copying conditions
1137 that are known to be false or true. */
1138 info
->conds
= vec_safe_copy (info
->conds
);
1140 /* When there are any replacements in the function body, see if we can figure
1141 out that something was optimized out. */
1142 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1144 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1145 /* Use SRC parm info since it may not be copied yet. */
1146 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1147 vec
<tree
> known_vals
= vNULL
;
1148 int count
= ipa_get_param_count (parms_info
);
1150 clause_t possible_truths
;
1151 struct predicate true_pred
= true_predicate ();
1153 int optimized_out_size
= 0;
1154 bool inlined_to_p
= false;
1155 struct cgraph_edge
*edge
, *next
;
1158 known_vals
.safe_grow_cleared (count
);
1159 for (i
= 0; i
< count
; i
++)
1161 struct ipa_replace_map
*r
;
1163 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1165 if (((!r
->old_tree
&& r
->parm_num
== i
)
1166 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1167 && r
->replace_p
&& !r
->ref_p
)
1169 known_vals
[i
] = r
->new_tree
;
1174 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1177 known_vals
.release ();
1179 account_size_time (info
, 0, 0, &true_pred
);
1181 /* Remap size_time vectors.
1182 Simplify the predicate by prunning out alternatives that are known
1184 TODO: as on optimization, we can also eliminate conditions known
1186 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1188 struct predicate new_predicate
;
1189 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1192 if (false_predicate_p (&new_predicate
))
1193 optimized_out_size
+= e
->size
;
1195 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1198 /* Remap edge predicates with the same simplification as above.
1199 Also copy constantness arrays. */
1200 for (edge
= dst
->callees
; edge
; edge
= next
)
1202 struct predicate new_predicate
;
1203 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1204 next
= edge
->next_callee
;
1206 if (!edge
->inline_failed
)
1207 inlined_to_p
= true;
1210 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1213 if (false_predicate_p (&new_predicate
)
1214 && !false_predicate_p (es
->predicate
))
1215 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1216 edge_set_predicate (edge
, &new_predicate
);
1219 /* Remap indirect edge predicates with the same simplificaiton as above.
1220 Also copy constantness arrays. */
1221 for (edge
= dst
->indirect_calls
; edge
; edge
= next
)
1223 struct predicate new_predicate
;
1224 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1225 next
= edge
->next_callee
;
1227 gcc_checking_assert (edge
->inline_failed
);
1230 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1233 if (false_predicate_p (&new_predicate
)
1234 && !false_predicate_p (es
->predicate
))
1235 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1236 edge_set_predicate (edge
, &new_predicate
);
1238 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1239 possible_truths
, info
);
1240 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1241 possible_truths
, info
);
1242 remap_hint_predicate_after_duplication (&info
->array_index
,
1243 possible_truths
, info
);
1245 /* If inliner or someone after inliner will ever start producing
1246 non-trivial clones, we will get trouble with lack of information
1247 about updating self sizes, because size vectors already contains
1248 sizes of the calees. */
1249 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1253 info
->entry
= vec_safe_copy (info
->entry
);
1254 if (info
->loop_iterations
)
1256 predicate p
= *info
->loop_iterations
;
1257 info
->loop_iterations
= NULL
;
1258 set_hint_predicate (&info
->loop_iterations
, p
);
1260 if (info
->loop_stride
)
1262 predicate p
= *info
->loop_stride
;
1263 info
->loop_stride
= NULL
;
1264 set_hint_predicate (&info
->loop_stride
, p
);
1266 if (info
->array_index
)
1268 predicate p
= *info
->array_index
;
1269 info
->array_index
= NULL
;
1270 set_hint_predicate (&info
->array_index
, p
);
1273 if (!dst
->global
.inlined_to
)
1274 inline_update_overall_summary (dst
);
1278 /* Hook that is called by cgraph.c when a node is duplicated. */
1281 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1282 struct cgraph_edge
*dst
,
1283 ATTRIBUTE_UNUSED
void *data
)
1285 struct inline_edge_summary
*info
;
1286 struct inline_edge_summary
*srcinfo
;
1287 inline_summary_alloc ();
1288 info
= inline_edge_summary (dst
);
1289 srcinfo
= inline_edge_summary (src
);
1290 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1291 info
->predicate
= NULL
;
1292 edge_set_predicate (dst
, srcinfo
->predicate
);
1293 info
->param
= srcinfo
->param
.copy ();
1294 if (!dst
->indirect_unknown_callee
&& src
->indirect_unknown_callee
)
1296 info
->call_stmt_size
-= (eni_size_weights
.indirect_call_cost
1297 - eni_size_weights
.call_cost
);
1298 info
->call_stmt_time
-= (eni_time_weights
.indirect_call_cost
1299 - eni_time_weights
.call_cost
);
1304 /* Keep edge cache consistent across edge removal. */
1307 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1308 void *data ATTRIBUTE_UNUSED
)
1310 if (edge_growth_cache
.exists ())
1311 reset_edge_growth_cache (edge
);
1312 reset_inline_edge_summary (edge
);
1316 /* Initialize growth caches. */
1319 initialize_growth_caches (void)
1321 if (symtab
->edges_max_uid
)
1322 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1326 /* Free growth caches. */
1329 free_growth_caches (void)
1331 edge_growth_cache
.release ();
1335 /* Dump edge summaries associated to NODE and recursively to all clones.
1336 Indent by INDENT. */
1339 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1340 struct inline_summary
*info
)
1342 struct cgraph_edge
*edge
;
1343 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1345 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1346 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1350 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1351 " time: %2i callee size:%2i stack:%2i",
1352 indent
, "", callee
->name (), callee
->order
,
1353 !edge
->inline_failed
1354 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1355 indent
, "", es
->loop_depth
, edge
->frequency
,
1356 es
->call_stmt_size
, es
->call_stmt_time
,
1357 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1358 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1362 fprintf (f
, " predicate: ");
1363 dump_predicate (f
, info
->conds
, es
->predicate
);
1367 if (es
->param
.exists ())
1368 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1370 int prob
= es
->param
[i
].change_prob
;
1373 fprintf (f
, "%*s op%i is compile time invariant\n",
1375 else if (prob
!= REG_BR_PROB_BASE
)
1376 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1377 prob
* 100.0 / REG_BR_PROB_BASE
);
1379 if (!edge
->inline_failed
)
1381 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1382 " callee size %i\n",
1384 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1385 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1386 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1387 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1390 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1392 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1393 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1397 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1400 fprintf (f
, "predicate: ");
1401 dump_predicate (f
, info
->conds
, es
->predicate
);
1410 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1412 if (node
->definition
)
1414 struct inline_summary
*s
= inline_summaries
->get (node
);
1417 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1419 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1420 fprintf (f
, " always_inline");
1422 fprintf (f
, " inlinable");
1423 if (s
->contains_cilk_spawn
)
1424 fprintf (f
, " contains_cilk_spawn");
1425 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1426 fprintf (f
, " global time: %i\n", s
->time
);
1427 fprintf (f
, " self size: %i\n", s
->self_size
);
1428 fprintf (f
, " global size: %i\n", s
->size
);
1429 fprintf (f
, " min size: %i\n", s
->min_size
);
1430 fprintf (f
, " self stack: %i\n",
1431 (int) s
->estimated_self_stack_size
);
1432 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1434 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1436 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1437 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1439 fprintf (f
, " size:%f, time:%f, predicate:",
1440 (double) e
->size
/ INLINE_SIZE_SCALE
,
1441 (double) e
->time
/ INLINE_TIME_SCALE
);
1442 dump_predicate (f
, s
->conds
, &e
->predicate
);
1444 if (s
->loop_iterations
)
1446 fprintf (f
, " loop iterations:");
1447 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1451 fprintf (f
, " loop stride:");
1452 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1456 fprintf (f
, " array index:");
1457 dump_predicate (f
, s
->conds
, s
->array_index
);
1459 fprintf (f
, " calls:\n");
1460 dump_inline_edge_summary (f
, 4, node
, s
);
1466 debug_inline_summary (struct cgraph_node
*node
)
1468 dump_inline_summary (stderr
, node
);
1472 dump_inline_summaries (FILE *f
)
1474 struct cgraph_node
*node
;
1476 FOR_EACH_DEFINED_FUNCTION (node
)
1477 if (!node
->global
.inlined_to
)
1478 dump_inline_summary (f
, node
);
1481 /* Give initial reasons why inlining would fail on EDGE. This gets either
1482 nullified or usually overwritten by more precise reasons later. */
1485 initialize_inline_failed (struct cgraph_edge
*e
)
1487 struct cgraph_node
*callee
= e
->callee
;
1489 if (e
->indirect_unknown_callee
)
1490 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1491 else if (!callee
->definition
)
1492 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1493 else if (callee
->local
.redefined_extern_inline
)
1494 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1495 else if (e
->call_stmt_cannot_inline_p
)
1496 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1497 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1498 /* We can't inline if the function is spawing a function. */
1499 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1501 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1504 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1505 boolean variable pointed to by DATA. */
1508 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1511 bool *b
= (bool *) data
;
1516 /* If OP refers to value of function parameter, return the corresponding
1520 unmodified_parm_1 (gimple
*stmt
, tree op
)
1522 /* SSA_NAME referring to parm default def? */
1523 if (TREE_CODE (op
) == SSA_NAME
1524 && SSA_NAME_IS_DEFAULT_DEF (op
)
1525 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1526 return SSA_NAME_VAR (op
);
1527 /* Non-SSA parm reference? */
1528 if (TREE_CODE (op
) == PARM_DECL
)
1530 bool modified
= false;
1533 ao_ref_init (&refd
, op
);
1534 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1542 /* If OP refers to value of function parameter, return the corresponding
1543 parameter. Also traverse chains of SSA register assignments. */
1546 unmodified_parm (gimple
*stmt
, tree op
)
1548 tree res
= unmodified_parm_1 (stmt
, op
);
1552 if (TREE_CODE (op
) == SSA_NAME
1553 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1554 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1555 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1556 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1560 /* If OP refers to a value of a function parameter or value loaded from an
1561 aggregate passed to a parameter (either by value or reference), return TRUE
1562 and store the number of the parameter to *INDEX_P and information whether
1563 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1564 the function parameters, STMT is the statement in which OP is used or
1568 unmodified_parm_or_parm_agg_item (struct ipa_func_body_info
*fbi
,
1569 gimple
*stmt
, tree op
, int *index_p
,
1570 struct agg_position_info
*aggpos
)
1572 tree res
= unmodified_parm_1 (stmt
, op
);
1574 gcc_checking_assert (aggpos
);
1577 *index_p
= ipa_get_param_decl_index (fbi
->info
, res
);
1580 aggpos
->agg_contents
= false;
1581 aggpos
->by_ref
= false;
1585 if (TREE_CODE (op
) == SSA_NAME
)
1587 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1588 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1590 stmt
= SSA_NAME_DEF_STMT (op
);
1591 op
= gimple_assign_rhs1 (stmt
);
1592 if (!REFERENCE_CLASS_P (op
))
1593 return unmodified_parm_or_parm_agg_item (fbi
, stmt
, op
, index_p
,
1597 aggpos
->agg_contents
= true;
1598 return ipa_load_from_parm_agg (fbi
, fbi
->info
->descriptors
,
1599 stmt
, op
, index_p
, &aggpos
->offset
,
1600 NULL
, &aggpos
->by_ref
);
1603 /* See if statement might disappear after inlining.
1604 0 - means not eliminated
1605 1 - half of statements goes away
1606 2 - for sure it is eliminated.
1607 We are not terribly sophisticated, basically looking for simple abstraction
1608 penalty wrappers. */
1611 eliminated_by_inlining_prob (gimple
*stmt
)
1613 enum gimple_code code
= gimple_code (stmt
);
1614 enum tree_code rhs_code
;
1624 if (gimple_num_ops (stmt
) != 2)
1627 rhs_code
= gimple_assign_rhs_code (stmt
);
1629 /* Casts of parameters, loads from parameters passed by reference
1630 and stores to return value or parameters are often free after
1631 inlining dua to SRA and further combining.
1632 Assume that half of statements goes away. */
1633 if (CONVERT_EXPR_CODE_P (rhs_code
)
1634 || rhs_code
== VIEW_CONVERT_EXPR
1635 || rhs_code
== ADDR_EXPR
1636 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1638 tree rhs
= gimple_assign_rhs1 (stmt
);
1639 tree lhs
= gimple_assign_lhs (stmt
);
1640 tree inner_rhs
= get_base_address (rhs
);
1641 tree inner_lhs
= get_base_address (lhs
);
1642 bool rhs_free
= false;
1643 bool lhs_free
= false;
1650 /* Reads of parameter are expected to be free. */
1651 if (unmodified_parm (stmt
, inner_rhs
))
1653 /* Match expressions of form &this->field. Those will most likely
1654 combine with something upstream after inlining. */
1655 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1657 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1658 if (TREE_CODE (op
) == PARM_DECL
)
1660 else if (TREE_CODE (op
) == MEM_REF
1661 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1665 /* When parameter is not SSA register because its address is taken
1666 and it is just copied into one, the statement will be completely
1667 free after inlining (we will copy propagate backward). */
1668 if (rhs_free
&& is_gimple_reg (lhs
))
1671 /* Reads of parameters passed by reference
1672 expected to be free (i.e. optimized out after inlining). */
1673 if (TREE_CODE (inner_rhs
) == MEM_REF
1674 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1677 /* Copying parameter passed by reference into gimple register is
1678 probably also going to copy propagate, but we can't be quite
1680 if (rhs_free
&& is_gimple_reg (lhs
))
1683 /* Writes to parameters, parameters passed by value and return value
1684 (either dirrectly or passed via invisible reference) are free.
1686 TODO: We ought to handle testcase like
1687 struct a {int a,b;};
1689 retrurnsturct (void)
1695 This translate into:
1710 For that we either need to copy ipa-split logic detecting writes
1712 if (TREE_CODE (inner_lhs
) == PARM_DECL
1713 || TREE_CODE (inner_lhs
) == RESULT_DECL
1714 || (TREE_CODE (inner_lhs
) == MEM_REF
1715 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1716 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1717 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1718 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1720 0))) == RESULT_DECL
))))
1723 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1725 if (lhs_free
&& rhs_free
)
1735 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1736 predicates to the CFG edges. */
1739 set_cond_stmt_execution_predicate (struct ipa_func_body_info
*fbi
,
1740 struct inline_summary
*summary
,
1746 struct agg_position_info aggpos
;
1747 enum tree_code code
, inverted_code
;
1753 last
= last_stmt (bb
);
1754 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1756 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1758 op
= gimple_cond_lhs (last
);
1759 /* TODO: handle conditionals like
1762 if (unmodified_parm_or_parm_agg_item (fbi
, last
, op
, &index
, &aggpos
))
1764 code
= gimple_cond_code (last
);
1765 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1767 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1769 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1770 ? code
: inverted_code
);
1771 /* invert_tree_comparison will return ERROR_MARK on FP
1772 comparsions that are not EQ/NE instead of returning proper
1773 unordered one. Be sure it is not confused with NON_CONSTANT. */
1774 if (this_code
!= ERROR_MARK
)
1776 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1778 gimple_cond_rhs (last
));
1779 e
->aux
= edge_predicate_pool
.allocate ();
1780 *(struct predicate
*) e
->aux
= p
;
1785 if (TREE_CODE (op
) != SSA_NAME
)
1788 if (builtin_constant_p (op))
1792 Here we can predicate nonconstant_code. We can't
1793 really handle constant_code since we have no predicate
1794 for this and also the constant code is not known to be
1795 optimized away when inliner doen't see operand is constant.
1796 Other optimizers might think otherwise. */
1797 if (gimple_cond_code (last
) != NE_EXPR
1798 || !integer_zerop (gimple_cond_rhs (last
)))
1800 set_stmt
= SSA_NAME_DEF_STMT (op
);
1801 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1802 || gimple_call_num_args (set_stmt
) != 1)
1804 op2
= gimple_call_arg (set_stmt
, 0);
1805 if (!unmodified_parm_or_parm_agg_item (fbi
, set_stmt
, op2
, &index
, &aggpos
))
1807 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1809 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1810 IS_NOT_CONSTANT
, NULL_TREE
);
1811 e
->aux
= edge_predicate_pool
.allocate ();
1812 *(struct predicate
*) e
->aux
= p
;
1817 /* If BB ends by a switch we can turn into predicates, attach corresponding
1818 predicates to the CFG edges. */
1821 set_switch_stmt_execution_predicate (struct ipa_func_body_info
*fbi
,
1822 struct inline_summary
*summary
,
1828 struct agg_position_info aggpos
;
1834 lastg
= last_stmt (bb
);
1835 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1837 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1838 op
= gimple_switch_index (last
);
1839 if (!unmodified_parm_or_parm_agg_item (fbi
, last
, op
, &index
, &aggpos
))
1842 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1844 e
->aux
= edge_predicate_pool
.allocate ();
1845 *(struct predicate
*) e
->aux
= false_predicate ();
1847 n
= gimple_switch_num_labels (last
);
1848 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1850 tree cl
= gimple_switch_label (last
, case_idx
);
1854 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1855 min
= CASE_LOW (cl
);
1856 max
= CASE_HIGH (cl
);
1858 /* For default we might want to construct predicate that none
1859 of cases is met, but it is bit hard to do not having negations
1860 of conditionals handy. */
1862 p
= true_predicate ();
1864 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1867 struct predicate p1
, p2
;
1868 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1869 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1870 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1872 *(struct predicate
*) e
->aux
1873 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1878 /* For each BB in NODE attach to its AUX pointer predicate under
1879 which it is executable. */
1882 compute_bb_predicates (struct ipa_func_body_info
*fbi
,
1883 struct cgraph_node
*node
,
1884 struct inline_summary
*summary
)
1886 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1890 FOR_EACH_BB_FN (bb
, my_function
)
1892 set_cond_stmt_execution_predicate (fbi
, summary
, bb
);
1893 set_switch_stmt_execution_predicate (fbi
, summary
, bb
);
1896 /* Entry block is always executable. */
1897 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1898 = edge_predicate_pool
.allocate ();
1899 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1900 = true_predicate ();
1902 /* A simple dataflow propagation of predicates forward in the CFG.
1903 TODO: work in reverse postorder. */
1907 FOR_EACH_BB_FN (bb
, my_function
)
1909 struct predicate p
= false_predicate ();
1912 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1916 struct predicate this_bb_predicate
1917 = *(struct predicate
*) e
->src
->aux
;
1920 = and_predicates (summary
->conds
, &this_bb_predicate
,
1921 (struct predicate
*) e
->aux
);
1922 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1923 if (true_predicate_p (&p
))
1927 if (false_predicate_p (&p
))
1928 gcc_assert (!bb
->aux
);
1934 bb
->aux
= edge_predicate_pool
.allocate ();
1935 *((struct predicate
*) bb
->aux
) = p
;
1937 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1939 /* This OR operation is needed to ensure monotonous data flow
1940 in the case we hit the limit on number of clauses and the
1941 and/or operations above give approximate answers. */
1942 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1943 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1946 *((struct predicate
*) bb
->aux
) = p
;
1955 /* We keep info about constantness of SSA names. */
1957 typedef struct predicate predicate_t
;
1958 /* Return predicate specifying when the STMT might have result that is not
1959 a compile time constant. */
1961 static struct predicate
1962 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1963 struct inline_summary
*summary
,
1965 vec
<predicate_t
> nonconstant_names
)
1970 while (UNARY_CLASS_P (expr
))
1971 expr
= TREE_OPERAND (expr
, 0);
1973 parm
= unmodified_parm (NULL
, expr
);
1974 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1975 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1976 if (is_gimple_min_invariant (expr
))
1977 return false_predicate ();
1978 if (TREE_CODE (expr
) == SSA_NAME
)
1979 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1980 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1982 struct predicate p1
= will_be_nonconstant_expr_predicate
1983 (info
, summary
, TREE_OPERAND (expr
, 0),
1985 struct predicate p2
;
1986 if (true_predicate_p (&p1
))
1988 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1989 TREE_OPERAND (expr
, 1),
1991 return or_predicates (summary
->conds
, &p1
, &p2
);
1993 else if (TREE_CODE (expr
) == COND_EXPR
)
1995 struct predicate p1
= will_be_nonconstant_expr_predicate
1996 (info
, summary
, TREE_OPERAND (expr
, 0),
1998 struct predicate p2
;
1999 if (true_predicate_p (&p1
))
2001 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2002 TREE_OPERAND (expr
, 1),
2004 if (true_predicate_p (&p2
))
2006 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2007 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2008 TREE_OPERAND (expr
, 2),
2010 return or_predicates (summary
->conds
, &p1
, &p2
);
2017 return false_predicate ();
2021 /* Return predicate specifying when the STMT might have result that is not
2022 a compile time constant. */
2024 static struct predicate
2025 will_be_nonconstant_predicate (struct ipa_func_body_info
*fbi
,
2026 struct inline_summary
*summary
,
2028 vec
<predicate_t
> nonconstant_names
)
2030 struct predicate p
= true_predicate ();
2033 struct predicate op_non_const
;
2036 struct agg_position_info aggpos
;
2038 /* What statments might be optimized away
2039 when their arguments are constant. */
2040 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2041 && gimple_code (stmt
) != GIMPLE_COND
2042 && gimple_code (stmt
) != GIMPLE_SWITCH
2043 && (gimple_code (stmt
) != GIMPLE_CALL
2044 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2047 /* Stores will stay anyway. */
2048 if (gimple_store_p (stmt
))
2051 is_load
= gimple_assign_load_p (stmt
);
2053 /* Loads can be optimized when the value is known. */
2057 gcc_assert (gimple_assign_single_p (stmt
));
2058 op
= gimple_assign_rhs1 (stmt
);
2059 if (!unmodified_parm_or_parm_agg_item (fbi
, stmt
, op
, &base_index
,
2066 /* See if we understand all operands before we start
2067 adding conditionals. */
2068 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2070 tree parm
= unmodified_parm (stmt
, use
);
2071 /* For arguments we can build a condition. */
2072 if (parm
&& ipa_get_param_decl_index (fbi
->info
, parm
) >= 0)
2074 if (TREE_CODE (use
) != SSA_NAME
)
2076 /* If we know when operand is constant,
2077 we still can say something useful. */
2078 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2085 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2087 op_non_const
= false_predicate ();
2088 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2090 tree parm
= unmodified_parm (stmt
, use
);
2093 if (parm
&& (index
= ipa_get_param_decl_index (fbi
->info
, parm
)) >= 0)
2095 if (index
!= base_index
)
2096 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2101 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2102 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2104 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2105 && gimple_op (stmt
, 0)
2106 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2107 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2109 return op_non_const
;
2112 struct record_modified_bb_info
2118 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2119 set except for info->stmt. */
2122 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2124 struct record_modified_bb_info
*info
=
2125 (struct record_modified_bb_info
*) data
;
2126 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2128 bitmap_set_bit (info
->bb_set
,
2129 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2130 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2131 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2135 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2136 will change since last invocation of STMT.
2138 Value 0 is reserved for compile time invariants.
2139 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2140 ought to be REG_BR_PROB_BASE / estimated_iters. */
2143 param_change_prob (gimple
*stmt
, int i
)
2145 tree op
= gimple_call_arg (stmt
, i
);
2146 basic_block bb
= gimple_bb (stmt
);
2149 /* Global invariants neve change. */
2150 if (is_gimple_min_invariant (op
))
2152 /* We would have to do non-trivial analysis to really work out what
2153 is the probability of value to change (i.e. when init statement
2154 is in a sibling loop of the call).
2156 We do an conservative estimate: when call is executed N times more often
2157 than the statement defining value, we take the frequency 1/N. */
2158 if (TREE_CODE (op
) == SSA_NAME
)
2163 return REG_BR_PROB_BASE
;
2165 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2166 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2168 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2172 if (init_freq
< bb
->frequency
)
2173 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2175 return REG_BR_PROB_BASE
;
2178 base
= get_base_address (op
);
2183 struct record_modified_bb_info info
;
2186 tree init
= ctor_for_folding (base
);
2188 if (init
!= error_mark_node
)
2191 return REG_BR_PROB_BASE
;
2192 ao_ref_init (&refd
, op
);
2194 info
.bb_set
= BITMAP_ALLOC (NULL
);
2195 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2197 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2199 BITMAP_FREE (info
.bb_set
);
2200 return REG_BR_PROB_BASE
;
2203 /* Assume that every memory is initialized at entry.
2204 TODO: Can we easilly determine if value is always defined
2205 and thus we may skip entry block? */
2206 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2207 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2211 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2212 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2214 BITMAP_FREE (info
.bb_set
);
2215 if (max
< bb
->frequency
)
2216 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2218 return REG_BR_PROB_BASE
;
2220 return REG_BR_PROB_BASE
;
2223 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2224 sub-graph and if the predicate the condition depends on is known. If so,
2225 return true and store the pointer the predicate in *P. */
2228 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2229 inline_summary
*summary
, basic_block bb
,
2230 struct predicate
*p
,
2231 vec
<predicate_t
> nonconstant_names
)
2235 basic_block first_bb
= NULL
;
2238 if (single_pred_p (bb
))
2240 *p
= false_predicate ();
2244 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2246 if (single_succ_p (e
->src
))
2248 if (!single_pred_p (e
->src
))
2251 first_bb
= single_pred (e
->src
);
2252 else if (single_pred (e
->src
) != first_bb
)
2259 else if (e
->src
!= first_bb
)
2267 stmt
= last_stmt (first_bb
);
2269 || gimple_code (stmt
) != GIMPLE_COND
2270 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2273 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2274 gimple_cond_lhs (stmt
),
2276 if (true_predicate_p (p
))
2282 /* Given a PHI statement in a function described by inline properties SUMMARY
2283 and *P being the predicate describing whether the selected PHI argument is
2284 known, store a predicate for the result of the PHI statement into
2285 NONCONSTANT_NAMES, if possible. */
2288 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2289 struct predicate
*p
,
2290 vec
<predicate_t
> nonconstant_names
)
2294 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2296 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2297 if (!is_gimple_min_invariant (arg
))
2299 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2300 *p
= or_predicates (summary
->conds
, p
,
2301 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2302 if (true_predicate_p (p
))
2307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2309 fprintf (dump_file
, "\t\tphi predicate: ");
2310 dump_predicate (dump_file
, summary
->conds
, p
);
2312 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2315 /* Return predicate specifying when array index in access OP becomes non-constant. */
2317 static struct predicate
2318 array_index_predicate (inline_summary
*info
,
2319 vec
< predicate_t
> nonconstant_names
, tree op
)
2321 struct predicate p
= false_predicate ();
2322 while (handled_component_p (op
))
2324 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2326 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2327 p
= or_predicates (info
->conds
, &p
,
2328 &nonconstant_names
[SSA_NAME_VERSION
2329 (TREE_OPERAND (op
, 1))]);
2331 op
= TREE_OPERAND (op
, 0);
2336 /* For a typical usage of __builtin_expect (a<b, 1), we
2337 may introduce an extra relation stmt:
2338 With the builtin, we have
2341 t3 = __builtin_expect (t2, 1);
2344 Without the builtin, we have
2347 This affects the size/time estimation and may have
2348 an impact on the earlier inlining.
2349 Here find this pattern and fix it up later. */
2352 find_foldable_builtin_expect (basic_block bb
)
2354 gimple_stmt_iterator bsi
;
2356 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2358 gimple
*stmt
= gsi_stmt (bsi
);
2359 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2360 || (is_gimple_call (stmt
)
2361 && gimple_call_internal_p (stmt
)
2362 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2364 tree var
= gimple_call_lhs (stmt
);
2365 tree arg
= gimple_call_arg (stmt
, 0);
2366 use_operand_p use_p
;
2373 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2375 while (TREE_CODE (arg
) == SSA_NAME
)
2377 gimple
*stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2378 if (!is_gimple_assign (stmt_tmp
))
2380 switch (gimple_assign_rhs_code (stmt_tmp
))
2399 arg
= gimple_assign_rhs1 (stmt_tmp
);
2402 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2403 && gimple_code (use_stmt
) == GIMPLE_COND
)
2410 /* Return true when the basic blocks contains only clobbers followed by RESX.
2411 Such BBs are kept around to make removal of dead stores possible with
2412 presence of EH and will be optimized out by optimize_clobbers later in the
2415 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2416 that can be clobber only, too.. When it is false, the RESX is not necessary
2417 on the end of basic block. */
2420 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2422 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2428 if (gsi_end_p (gsi
))
2430 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2434 else if (!single_succ_p (bb
))
2437 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2439 gimple
*stmt
= gsi_stmt (gsi
);
2440 if (is_gimple_debug (stmt
))
2442 if (gimple_clobber_p (stmt
))
2444 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2449 /* See if all predecestors are either throws or clobber only BBs. */
2450 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2451 if (!(e
->flags
& EDGE_EH
)
2452 && !clobber_only_eh_bb_p (e
->src
, false))
2458 /* Compute function body size parameters for NODE.
2459 When EARLY is true, we compute only simple summaries without
2460 non-trivial predicates to drive the early inliner. */
2463 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2466 /* Estimate static overhead for function prologue/epilogue and alignment. */
2468 /* Benefits are scaled by probability of elimination that is in range
2471 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2473 struct inline_summary
*info
= inline_summaries
->get (node
);
2474 struct predicate bb_predicate
;
2475 struct ipa_func_body_info fbi
;
2476 vec
<predicate_t
> nonconstant_names
= vNULL
;
2479 predicate array_index
= true_predicate ();
2480 gimple
*fix_builtin_expect_stmt
;
2482 gcc_assert (my_function
&& my_function
->cfg
);
2483 gcc_assert (cfun
== my_function
);
2485 memset(&fbi
, 0, sizeof(fbi
));
2489 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2490 so we can produce proper inline hints.
2492 When optimizing and analyzing for early inliner, initialize node params
2493 so we can produce correct BB predicates. */
2495 if (opt_for_fn (node
->decl
, optimize
))
2497 calculate_dominance_info (CDI_DOMINATORS
);
2499 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2502 ipa_check_create_node_params ();
2503 ipa_initialize_node_params (node
);
2506 if (ipa_node_params_sum
)
2509 fbi
.info
= IPA_NODE_REF (node
);
2510 fbi
.bb_infos
= vNULL
;
2511 fbi
.bb_infos
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
2512 fbi
.param_count
= count_formal_params(node
->decl
);
2513 nonconstant_names
.safe_grow_cleared
2514 (SSANAMES (my_function
)->length ());
2519 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2522 /* When we run into maximal number of entries, we assign everything to the
2523 constant truth case. Be sure to have it in list. */
2524 bb_predicate
= true_predicate ();
2525 account_size_time (info
, 0, 0, &bb_predicate
);
2527 bb_predicate
= not_inlined_predicate ();
2528 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2531 compute_bb_predicates (&fbi
, node
, info
);
2532 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2533 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2534 for (n
= 0; n
< nblocks
; n
++)
2536 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2537 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2538 if (clobber_only_eh_bb_p (bb
))
2540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2541 fprintf (dump_file
, "\n Ignoring BB %i;"
2542 " it will be optimized away by cleanup_clobbers\n",
2547 /* TODO: Obviously predicates can be propagated down across CFG. */
2551 bb_predicate
= *(struct predicate
*) bb
->aux
;
2553 bb_predicate
= false_predicate ();
2556 bb_predicate
= true_predicate ();
2558 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2560 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2561 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2564 if (fbi
.info
&& nonconstant_names
.exists ())
2566 struct predicate phi_predicate
;
2567 bool first_phi
= true;
2569 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2573 && !phi_result_unknown_predicate (fbi
.info
, info
, bb
,
2578 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2580 fprintf (dump_file
, " ");
2581 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2583 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2588 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2590 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2593 gimple
*stmt
= gsi_stmt (bsi
);
2594 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2595 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2597 struct predicate will_be_nonconstant
;
2599 /* This relation stmt should be folded after we remove
2600 buildin_expect call. Adjust the cost here. */
2601 if (stmt
== fix_builtin_expect_stmt
)
2607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2609 fprintf (dump_file
, " ");
2610 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2611 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2612 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2616 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2618 struct predicate this_array_index
;
2620 array_index_predicate (info
, nonconstant_names
,
2621 gimple_assign_rhs1 (stmt
));
2622 if (!false_predicate_p (&this_array_index
))
2624 and_predicates (info
->conds
, &array_index
,
2627 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2629 struct predicate this_array_index
;
2631 array_index_predicate (info
, nonconstant_names
,
2632 gimple_get_lhs (stmt
));
2633 if (!false_predicate_p (&this_array_index
))
2635 and_predicates (info
->conds
, &array_index
,
2640 if (is_gimple_call (stmt
)
2641 && !gimple_call_internal_p (stmt
))
2643 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2644 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2646 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2647 resolved as constant. We however don't want to optimize
2648 out the cgraph edges. */
2649 if (nonconstant_names
.exists ()
2650 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2651 && gimple_call_lhs (stmt
)
2652 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2654 struct predicate false_p
= false_predicate ();
2655 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2658 if (ipa_node_params_sum
)
2660 int count
= gimple_call_num_args (stmt
);
2664 es
->param
.safe_grow_cleared (count
);
2665 for (i
= 0; i
< count
; i
++)
2667 int prob
= param_change_prob (stmt
, i
);
2668 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2669 es
->param
[i
].change_prob
= prob
;
2673 es
->call_stmt_size
= this_size
;
2674 es
->call_stmt_time
= this_time
;
2675 es
->loop_depth
= bb_loop_depth (bb
);
2676 edge_set_predicate (edge
, &bb_predicate
);
2679 /* TODO: When conditional jump or swithc is known to be constant, but
2680 we did not translate it into the predicates, we really can account
2681 just maximum of the possible paths. */
2684 = will_be_nonconstant_predicate (&fbi
, info
,
2685 stmt
, nonconstant_names
);
2686 if (this_time
|| this_size
)
2692 prob
= eliminated_by_inlining_prob (stmt
);
2693 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2695 "\t\t50%% will be eliminated by inlining\n");
2696 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2697 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2700 p
= and_predicates (info
->conds
, &bb_predicate
,
2701 &will_be_nonconstant
);
2703 p
= true_predicate ();
2705 if (!false_predicate_p (&p
)
2706 || (is_gimple_call (stmt
)
2707 && !false_predicate_p (&bb_predicate
)))
2711 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2712 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2715 /* We account everything but the calls. Calls have their own
2716 size/time info attached to cgraph edges. This is necessary
2717 in order to make the cost disappear after inlining. */
2718 if (!is_gimple_call (stmt
))
2722 struct predicate ip
= not_inlined_predicate ();
2723 ip
= and_predicates (info
->conds
, &ip
, &p
);
2724 account_size_time (info
, this_size
* prob
,
2725 this_time
* prob
, &ip
);
2728 account_size_time (info
, this_size
* (2 - prob
),
2729 this_time
* (2 - prob
), &p
);
2732 gcc_assert (time
>= 0);
2733 gcc_assert (size
>= 0);
2737 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2738 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2739 if (time
> MAX_TIME
)
2743 if (nonconstant_names
.exists () && !early
)
2746 predicate loop_iterations
= true_predicate ();
2747 predicate loop_stride
= true_predicate ();
2749 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2750 flow_loops_dump (dump_file
, NULL
, 0);
2752 FOR_EACH_LOOP (loop
, 0)
2757 struct tree_niter_desc niter_desc
;
2758 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2760 exits
= get_loop_exit_edges (loop
);
2761 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2762 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2763 && !is_gimple_min_invariant (niter_desc
.niter
))
2765 predicate will_be_nonconstant
2766 = will_be_nonconstant_expr_predicate (fbi
.info
, info
,
2769 if (!true_predicate_p (&will_be_nonconstant
))
2770 will_be_nonconstant
= and_predicates (info
->conds
,
2772 &will_be_nonconstant
);
2773 if (!true_predicate_p (&will_be_nonconstant
)
2774 && !false_predicate_p (&will_be_nonconstant
))
2775 /* This is slightly inprecise. We may want to represent each
2776 loop with independent predicate. */
2778 and_predicates (info
->conds
, &loop_iterations
,
2779 &will_be_nonconstant
);
2784 /* To avoid quadratic behavior we analyze stride predicates only
2785 with respect to the containing loop. Thus we simply iterate
2786 over all defs in the outermost loop body. */
2787 for (loop
= loops_for_fn (cfun
)->tree_root
->inner
;
2788 loop
!= NULL
; loop
= loop
->next
)
2790 basic_block
*body
= get_loop_body (loop
);
2791 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
2793 gimple_stmt_iterator gsi
;
2794 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2795 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2798 gimple
*stmt
= gsi_stmt (gsi
);
2800 if (!is_gimple_assign (stmt
))
2803 tree def
= gimple_assign_lhs (stmt
);
2804 if (TREE_CODE (def
) != SSA_NAME
)
2808 if (!simple_iv (loop_containing_stmt (stmt
),
2809 loop_containing_stmt (stmt
),
2811 || is_gimple_min_invariant (iv
.step
))
2814 predicate will_be_nonconstant
2815 = will_be_nonconstant_expr_predicate (fbi
.info
, info
,
2818 if (!true_predicate_p (&will_be_nonconstant
))
2820 = and_predicates (info
->conds
, &bb_predicate
,
2821 &will_be_nonconstant
);
2822 if (!true_predicate_p (&will_be_nonconstant
)
2823 && !false_predicate_p (&will_be_nonconstant
))
2824 /* This is slightly inprecise. We may want to represent
2825 each loop with independent predicate. */
2826 loop_stride
= and_predicates (info
->conds
, &loop_stride
,
2827 &will_be_nonconstant
);
2832 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2834 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
,
2838 FOR_ALL_BB_FN (bb
, my_function
)
2844 edge_predicate_pool
.remove ((predicate
*)bb
->aux
);
2846 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2849 edge_predicate_pool
.remove ((predicate
*) e
->aux
);
2853 inline_summaries
->get (node
)->self_time
= time
;
2854 inline_summaries
->get (node
)->self_size
= size
;
2855 nonconstant_names
.release ();
2856 ipa_release_body_info (&fbi
);
2857 if (opt_for_fn (node
->decl
, optimize
))
2860 loop_optimizer_finalize ();
2861 else if (!ipa_edge_args_vector
)
2862 ipa_free_all_node_params ();
2863 free_dominance_info (CDI_DOMINATORS
);
2867 fprintf (dump_file
, "\n");
2868 dump_inline_summary (dump_file
, node
);
2873 /* Compute parameters of functions used by inliner.
2874 EARLY is true when we compute parameters for the early inliner */
2877 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2879 HOST_WIDE_INT self_stack_size
;
2880 struct cgraph_edge
*e
;
2881 struct inline_summary
*info
;
2883 gcc_assert (!node
->global
.inlined_to
);
2885 inline_summary_alloc ();
2887 info
= inline_summaries
->get (node
);
2888 reset_inline_summary (node
, info
);
2890 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2891 Once this happen, we will need to more curefully predict call
2893 if (node
->thunk
.thunk_p
)
2895 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2896 struct predicate t
= true_predicate ();
2898 info
->inlinable
= 0;
2899 node
->callees
->call_stmt_cannot_inline_p
= true;
2900 node
->local
.can_change_signature
= false;
2901 es
->call_stmt_time
= 1;
2902 es
->call_stmt_size
= 1;
2903 account_size_time (info
, 0, 0, &t
);
2907 /* Even is_gimple_min_invariant rely on current_function_decl. */
2908 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2910 /* Estimate the stack size for the function if we're optimizing. */
2911 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2912 info
->estimated_self_stack_size
= self_stack_size
;
2913 info
->estimated_stack_size
= self_stack_size
;
2914 info
->stack_frame_offset
= 0;
2916 /* Can this function be inlined at all? */
2917 if (!opt_for_fn (node
->decl
, optimize
)
2918 && !lookup_attribute ("always_inline",
2919 DECL_ATTRIBUTES (node
->decl
)))
2920 info
->inlinable
= false;
2922 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2924 info
->contains_cilk_spawn
= fn_contains_cilk_spawn_p (cfun
);
2926 /* Type attributes can use parameter indices to describe them. */
2927 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2928 node
->local
.can_change_signature
= false;
2931 /* Otherwise, inlinable functions always can change signature. */
2932 if (info
->inlinable
)
2933 node
->local
.can_change_signature
= true;
2936 /* Functions calling builtin_apply can not change signature. */
2937 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2939 tree
cdecl = e
->callee
->decl
;
2940 if (DECL_BUILT_IN (cdecl)
2941 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2942 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2943 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2946 node
->local
.can_change_signature
= !e
;
2949 estimate_function_body_sizes (node
, early
);
2951 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2952 if (e
->callee
->comdat_local_p ())
2954 node
->calls_comdat_local
= (e
!= NULL
);
2956 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2957 info
->time
= info
->self_time
;
2958 info
->size
= info
->self_size
;
2959 info
->stack_frame_offset
= 0;
2960 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2963 inline_update_overall_summary (node
);
2964 gcc_assert (info
->time
== info
->self_time
2965 && info
->size
== info
->self_size
);
2972 /* Compute parameters of functions used by inliner using
2973 current_function_decl. */
2976 compute_inline_parameters_for_current (void)
2978 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2984 const pass_data pass_data_inline_parameters
=
2986 GIMPLE_PASS
, /* type */
2987 "inline_param", /* name */
2988 OPTGROUP_INLINE
, /* optinfo_flags */
2989 TV_INLINE_PARAMETERS
, /* tv_id */
2990 0, /* properties_required */
2991 0, /* properties_provided */
2992 0, /* properties_destroyed */
2993 0, /* todo_flags_start */
2994 0, /* todo_flags_finish */
2997 class pass_inline_parameters
: public gimple_opt_pass
3000 pass_inline_parameters (gcc::context
*ctxt
)
3001 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
3004 /* opt_pass methods: */
3005 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
3006 virtual unsigned int execute (function
*)
3008 return compute_inline_parameters_for_current ();
3011 }; // class pass_inline_parameters
3016 make_pass_inline_parameters (gcc::context
*ctxt
)
3018 return new pass_inline_parameters (ctxt
);
3022 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3023 KNOWN_CONTEXTS and KNOWN_AGGS. */
3026 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3027 int *size
, int *time
,
3028 vec
<tree
> known_vals
,
3029 vec
<ipa_polymorphic_call_context
> known_contexts
,
3030 vec
<ipa_agg_jump_function_p
> known_aggs
)
3033 struct cgraph_node
*callee
;
3034 struct inline_summary
*isummary
;
3035 enum availability avail
;
3038 if (!known_vals
.exists () && !known_contexts
.exists ())
3040 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3043 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3044 known_aggs
, &speculative
);
3045 if (!target
|| speculative
)
3048 /* Account for difference in cost between indirect and direct calls. */
3049 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3050 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3051 gcc_checking_assert (*time
>= 0);
3052 gcc_checking_assert (*size
>= 0);
3054 callee
= cgraph_node::get (target
);
3055 if (!callee
|| !callee
->definition
)
3057 callee
= callee
->function_symbol (&avail
);
3058 if (avail
< AVAIL_AVAILABLE
)
3060 isummary
= inline_summaries
->get (callee
);
3061 return isummary
->inlinable
;
3064 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3065 handle edge E with probability PROB.
3066 Set HINTS if edge may be devirtualized.
3067 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3071 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3074 vec
<tree
> known_vals
,
3075 vec
<ipa_polymorphic_call_context
> known_contexts
,
3076 vec
<ipa_agg_jump_function_p
> known_aggs
,
3077 inline_hints
*hints
)
3079 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3080 int call_size
= es
->call_stmt_size
;
3081 int call_time
= es
->call_stmt_time
;
3084 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3085 known_vals
, known_contexts
, known_aggs
)
3086 && hints
&& e
->maybe_hot_p ())
3087 *hints
|= INLINE_HINT_indirect_call
;
3088 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3091 *min_size
+= cur_size
;
3092 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3093 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3094 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3095 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3100 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3101 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3102 describe context of the call site. */
3105 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3106 int *min_size
, int *time
,
3107 inline_hints
*hints
,
3108 clause_t possible_truths
,
3109 vec
<tree
> known_vals
,
3110 vec
<ipa_polymorphic_call_context
> known_contexts
,
3111 vec
<ipa_agg_jump_function_p
> known_aggs
)
3113 struct cgraph_edge
*e
;
3114 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3116 if (inline_edge_summary_vec
.length () <= (unsigned) e
->uid
)
3119 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3121 /* Do not care about zero sized builtins. */
3122 if (e
->inline_failed
&& !es
->call_stmt_size
)
3124 gcc_checking_assert (!es
->call_stmt_time
);
3128 || evaluate_predicate (es
->predicate
, possible_truths
))
3130 if (e
->inline_failed
)
3132 /* Predicates of calls shall not use NOT_CHANGED codes,
3133 sowe do not need to compute probabilities. */
3134 estimate_edge_size_and_time (e
, size
,
3135 es
->predicate
? NULL
: min_size
,
3136 time
, REG_BR_PROB_BASE
,
3137 known_vals
, known_contexts
,
3141 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3144 known_vals
, known_contexts
,
3148 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3150 if (inline_edge_summary_vec
.length () <= (unsigned) e
->uid
)
3153 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3155 || evaluate_predicate (es
->predicate
, possible_truths
))
3156 estimate_edge_size_and_time (e
, size
,
3157 es
->predicate
? NULL
: min_size
,
3158 time
, REG_BR_PROB_BASE
,
3159 known_vals
, known_contexts
, known_aggs
,
3165 /* Estimate size and time needed to execute NODE assuming
3166 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3167 information about NODE's arguments. If non-NULL use also probability
3168 information present in INLINE_PARAM_SUMMARY vector.
3169 Additionally detemine hints determined by the context. Finally compute
3170 minimal size needed for the call that is independent on the call context and
3171 can be used for fast estimates. Return the values in RET_SIZE,
3172 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3175 estimate_node_size_and_time (struct cgraph_node
*node
,
3176 clause_t possible_truths
,
3177 vec
<tree
> known_vals
,
3178 vec
<ipa_polymorphic_call_context
> known_contexts
,
3179 vec
<ipa_agg_jump_function_p
> known_aggs
,
3180 int *ret_size
, int *ret_min_size
, int *ret_time
,
3181 inline_hints
*ret_hints
,
3182 vec
<inline_param_summary
>
3183 inline_param_summary
)
3185 struct inline_summary
*info
= inline_summaries
->get (node
);
3190 inline_hints hints
= 0;
3193 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3196 fprintf (dump_file
, " Estimating body: %s/%i\n"
3197 " Known to be false: ", node
->name (),
3200 for (i
= predicate_not_inlined_condition
;
3201 i
< (predicate_first_dynamic_condition
3202 + (int) vec_safe_length (info
->conds
)); i
++)
3203 if (!(possible_truths
& (1 << i
)))
3206 fprintf (dump_file
, ", ");
3208 dump_condition (dump_file
, info
->conds
, i
);
3212 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3213 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3216 gcc_checking_assert (e
->time
>= 0);
3217 gcc_checking_assert (time
>= 0);
3218 if (!inline_param_summary
.exists ())
3222 int prob
= predicate_probability (info
->conds
,
3225 inline_param_summary
);
3226 gcc_checking_assert (prob
>= 0);
3227 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3228 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3230 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3231 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3232 gcc_checking_assert (time
>= 0);
3235 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3236 min_size
= (*info
->entry
)[0].size
;
3237 gcc_checking_assert (size
>= 0);
3238 gcc_checking_assert (time
>= 0);
3240 if (info
->loop_iterations
3241 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3242 hints
|= INLINE_HINT_loop_iterations
;
3243 if (info
->loop_stride
3244 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3245 hints
|= INLINE_HINT_loop_stride
;
3246 if (info
->array_index
3247 && !evaluate_predicate (info
->array_index
, possible_truths
))
3248 hints
|= INLINE_HINT_array_index
;
3250 hints
|= INLINE_HINT_in_scc
;
3251 if (DECL_DECLARED_INLINE_P (node
->decl
))
3252 hints
|= INLINE_HINT_declared_inline
;
3254 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3255 known_vals
, known_contexts
, known_aggs
);
3256 gcc_checking_assert (size
>= 0);
3257 gcc_checking_assert (time
>= 0);
3258 time
= RDIV (time
, INLINE_TIME_SCALE
);
3259 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3260 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3262 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3263 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3269 *ret_min_size
= min_size
;
3276 /* Estimate size and time needed to execute callee of EDGE assuming that
3277 parameters known to be constant at caller of EDGE are propagated.
3278 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3279 and types for parameters. */
3282 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3283 vec
<tree
> known_vals
,
3284 vec
<ipa_polymorphic_call_context
>
3286 vec
<ipa_agg_jump_function_p
> known_aggs
,
3287 int *ret_size
, int *ret_time
,
3288 inline_hints
*hints
)
3292 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3294 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3295 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3298 /* Translate all conditions from callee representation into caller
3299 representation and symbolically evaluate predicate P into new predicate.
3301 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3302 is summary of function predicate P is from. OPERAND_MAP is array giving
3303 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3304 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3305 predicate under which callee is executed. OFFSET_MAP is an array of of
3306 offsets that need to be added to conditions, negative offset means that
3307 conditions relying on values passed by reference have to be discarded
3308 because they might not be preserved (and should be considered offset zero
3309 for other purposes). */
3311 static struct predicate
3312 remap_predicate (struct inline_summary
*info
,
3313 struct inline_summary
*callee_info
,
3314 struct predicate
*p
,
3315 vec
<int> operand_map
,
3316 vec
<int> offset_map
,
3317 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3320 struct predicate out
= true_predicate ();
3322 /* True predicate is easy. */
3323 if (true_predicate_p (p
))
3324 return *toplev_predicate
;
3325 for (i
= 0; p
->clause
[i
]; i
++)
3327 clause_t clause
= p
->clause
[i
];
3329 struct predicate clause_predicate
= false_predicate ();
3331 gcc_assert (i
< MAX_CLAUSES
);
3333 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3334 /* Do we have condition we can't disprove? */
3335 if (clause
& possible_truths
& (1 << cond
))
3337 struct predicate cond_predicate
;
3338 /* Work out if the condition can translate to predicate in the
3339 inlined function. */
3340 if (cond
>= predicate_first_dynamic_condition
)
3342 struct condition
*c
;
3344 c
= &(*callee_info
->conds
)[cond
3346 predicate_first_dynamic_condition
];
3347 /* See if we can remap condition operand to caller's operand.
3348 Otherwise give up. */
3349 if (!operand_map
.exists ()
3350 || (int) operand_map
.length () <= c
->operand_num
3351 || operand_map
[c
->operand_num
] == -1
3352 /* TODO: For non-aggregate conditions, adding an offset is
3353 basically an arithmetic jump function processing which
3354 we should support in future. */
3355 || ((!c
->agg_contents
|| !c
->by_ref
)
3356 && offset_map
[c
->operand_num
] > 0)
3357 || (c
->agg_contents
&& c
->by_ref
3358 && offset_map
[c
->operand_num
] < 0))
3359 cond_predicate
= true_predicate ();
3362 struct agg_position_info ap
;
3363 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3364 if (offset_delta
< 0)
3366 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3369 gcc_assert (!c
->agg_contents
3370 || c
->by_ref
|| offset_delta
== 0);
3371 ap
.offset
= c
->offset
+ offset_delta
;
3372 ap
.agg_contents
= c
->agg_contents
;
3373 ap
.by_ref
= c
->by_ref
;
3374 cond_predicate
= add_condition (info
,
3375 operand_map
[c
->operand_num
],
3376 &ap
, c
->code
, c
->val
);
3379 /* Fixed conditions remains same, construct single
3380 condition predicate. */
3383 cond_predicate
.clause
[0] = 1 << cond
;
3384 cond_predicate
.clause
[1] = 0;
3386 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3389 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3391 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3395 /* Update summary information of inline clones after inlining.
3396 Compute peak stack usage. */
3399 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3401 struct cgraph_edge
*e
;
3402 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3403 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3406 callee_info
->stack_frame_offset
3407 = caller_info
->stack_frame_offset
3408 + caller_info
->estimated_self_stack_size
;
3409 peak
= callee_info
->stack_frame_offset
3410 + callee_info
->estimated_self_stack_size
;
3411 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3412 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3413 ipa_propagate_frequency (node
);
3414 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3416 if (!e
->inline_failed
)
3417 inline_update_callee_summaries (e
->callee
, depth
);
3418 inline_edge_summary (e
)->loop_depth
+= depth
;
3420 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3421 inline_edge_summary (e
)->loop_depth
+= depth
;
3424 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3425 When functoin A is inlined in B and A calls C with parameter that
3426 changes with probability PROB1 and C is known to be passthroug
3427 of argument if B that change with probability PROB2, the probability
3428 of change is now PROB1*PROB2. */
3431 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3432 struct cgraph_edge
*edge
)
3434 if (ipa_node_params_sum
)
3437 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3438 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3439 struct inline_edge_summary
*inlined_es
3440 = inline_edge_summary (inlined_edge
);
3442 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3444 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3445 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3446 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3447 < (int) inlined_es
->param
.length ()))
3449 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3450 int prob1
= es
->param
[i
].change_prob
;
3451 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3452 int prob
= combine_probabilities (prob1
, prob2
);
3454 if (prob1
&& prob2
&& !prob
)
3457 es
->param
[i
].change_prob
= prob
;
3463 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3465 Remap predicates of callees of NODE. Rest of arguments match
3468 Also update change probabilities. */
3471 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3472 struct cgraph_node
*node
,
3473 struct inline_summary
*info
,
3474 struct inline_summary
*callee_info
,
3475 vec
<int> operand_map
,
3476 vec
<int> offset_map
,
3477 clause_t possible_truths
,
3478 struct predicate
*toplev_predicate
)
3480 struct cgraph_edge
*e
, *next
;
3481 for (e
= node
->callees
; e
; e
= next
)
3483 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3485 next
= e
->next_callee
;
3487 if (e
->inline_failed
)
3489 remap_edge_change_prob (inlined_edge
, e
);
3493 p
= remap_predicate (info
, callee_info
,
3494 es
->predicate
, operand_map
, offset_map
,
3495 possible_truths
, toplev_predicate
);
3496 edge_set_predicate (e
, &p
);
3499 edge_set_predicate (e
, toplev_predicate
);
3502 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3503 operand_map
, offset_map
, possible_truths
,
3506 for (e
= node
->indirect_calls
; e
; e
= next
)
3508 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3510 next
= e
->next_callee
;
3512 remap_edge_change_prob (inlined_edge
, e
);
3515 p
= remap_predicate (info
, callee_info
,
3516 es
->predicate
, operand_map
, offset_map
,
3517 possible_truths
, toplev_predicate
);
3518 edge_set_predicate (e
, &p
);
3521 edge_set_predicate (e
, toplev_predicate
);
3525 /* Same as remap_predicate, but set result into hint *HINT. */
3528 remap_hint_predicate (struct inline_summary
*info
,
3529 struct inline_summary
*callee_info
,
3530 struct predicate
**hint
,
3531 vec
<int> operand_map
,
3532 vec
<int> offset_map
,
3533 clause_t possible_truths
,
3534 struct predicate
*toplev_predicate
)
3540 p
= remap_predicate (info
, callee_info
,
3542 operand_map
, offset_map
,
3543 possible_truths
, toplev_predicate
);
3544 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3547 set_hint_predicate (hint
, p
);
3549 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3553 /* We inlined EDGE. Update summary of the function we inlined into. */
3556 inline_merge_summary (struct cgraph_edge
*edge
)
3558 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3559 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3560 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3561 struct inline_summary
*info
= inline_summaries
->get (to
);
3562 clause_t clause
= 0; /* not_inline is known to be false. */
3564 vec
<int> operand_map
= vNULL
;
3565 vec
<int> offset_map
= vNULL
;
3567 struct predicate toplev_predicate
;
3568 struct predicate true_p
= true_predicate ();
3569 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3572 toplev_predicate
= *es
->predicate
;
3574 toplev_predicate
= true_predicate ();
3576 if (callee_info
->conds
)
3577 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3578 if (ipa_node_params_sum
&& callee_info
->conds
)
3580 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3581 int count
= ipa_get_cs_argument_count (args
);
3586 operand_map
.safe_grow_cleared (count
);
3587 offset_map
.safe_grow_cleared (count
);
3589 for (i
= 0; i
< count
; i
++)
3591 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3594 /* TODO: handle non-NOPs when merging. */
3595 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3597 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3598 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3599 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3602 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3604 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3605 if (offset
>= 0 && offset
< INT_MAX
)
3607 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3608 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3610 offset_map
[i
] = offset
;
3613 operand_map
[i
] = map
;
3614 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3617 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3619 struct predicate p
= remap_predicate (info
, callee_info
,
3620 &e
->predicate
, operand_map
,
3623 if (!false_predicate_p (&p
))
3625 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3626 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3627 int prob
= predicate_probability (callee_info
->conds
,
3630 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3631 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3632 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3633 if (prob
!= REG_BR_PROB_BASE
3634 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3636 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3637 (double) prob
/ REG_BR_PROB_BASE
);
3639 account_size_time (info
, e
->size
, add_time
, &p
);
3642 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3643 offset_map
, clause
, &toplev_predicate
);
3644 remap_hint_predicate (info
, callee_info
,
3645 &callee_info
->loop_iterations
,
3646 operand_map
, offset_map
, clause
, &toplev_predicate
);
3647 remap_hint_predicate (info
, callee_info
,
3648 &callee_info
->loop_stride
,
3649 operand_map
, offset_map
, clause
, &toplev_predicate
);
3650 remap_hint_predicate (info
, callee_info
,
3651 &callee_info
->array_index
,
3652 operand_map
, offset_map
, clause
, &toplev_predicate
);
3654 inline_update_callee_summaries (edge
->callee
,
3655 inline_edge_summary (edge
)->loop_depth
);
3657 /* We do not maintain predicates of inlined edges, free it. */
3658 edge_set_predicate (edge
, &true_p
);
3659 /* Similarly remove param summaries. */
3660 es
->param
.release ();
3661 operand_map
.release ();
3662 offset_map
.release ();
3665 /* For performance reasons inline_merge_summary is not updating overall size
3666 and time. Recompute it. */
3669 inline_update_overall_summary (struct cgraph_node
*node
)
3671 struct inline_summary
*info
= inline_summaries
->get (node
);
3677 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3679 info
->size
+= e
->size
, info
->time
+= e
->time
;
3680 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3681 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3683 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3685 ~(clause_t
) (1 << predicate_false_condition
),
3686 vNULL
, vNULL
, vNULL
);
3687 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3688 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3691 /* Return hints derrived from EDGE. */
3693 simple_edge_hints (struct cgraph_edge
*edge
)
3696 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3697 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3698 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
3699 if (inline_summaries
->get (to
)->scc_no
3700 && inline_summaries
->get (to
)->scc_no
3701 == inline_summaries
->get (callee
)->scc_no
3702 && !edge
->recursive_p ())
3703 hints
|= INLINE_HINT_same_scc
;
3705 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
3706 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
3708 hints
|= INLINE_HINT_cross_module
;
3713 /* Estimate the time cost for the caller when inlining EDGE.
3714 Only to be called via estimate_edge_time, that handles the
3717 When caching, also update the cache entry. Compute both time and
3718 size, since we always need both metrics eventually. */
3721 do_estimate_edge_time (struct cgraph_edge
*edge
)
3726 struct cgraph_node
*callee
;
3728 vec
<tree
> known_vals
;
3729 vec
<ipa_polymorphic_call_context
> known_contexts
;
3730 vec
<ipa_agg_jump_function_p
> known_aggs
;
3731 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3734 callee
= edge
->callee
->ultimate_alias_target ();
3736 gcc_checking_assert (edge
->inline_failed
);
3737 evaluate_properties_for_edge (edge
, true,
3738 &clause
, &known_vals
, &known_contexts
,
3740 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3741 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3743 /* When we have profile feedback, we can quite safely identify hot
3744 edges and for those we disable size limits. Don't do that when
3745 probability that caller will call the callee is low however, since it
3746 may hurt optimization of the caller's hot path. */
3747 if (edge
->count
&& edge
->maybe_hot_p ()
3749 > (edge
->caller
->global
.inlined_to
3750 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3751 hints
|= INLINE_HINT_known_hot
;
3753 known_vals
.release ();
3754 known_contexts
.release ();
3755 known_aggs
.release ();
3756 gcc_checking_assert (size
>= 0);
3757 gcc_checking_assert (time
>= 0);
3759 /* When caching, update the cache entry. */
3760 if (edge_growth_cache
.exists ())
3762 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3763 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3764 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3765 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3767 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3768 hints
|= simple_edge_hints (edge
);
3769 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3775 /* Return estimated callee growth after inlining EDGE.
3776 Only to be called via estimate_edge_size. */
3779 do_estimate_edge_size (struct cgraph_edge
*edge
)
3782 struct cgraph_node
*callee
;
3784 vec
<tree
> known_vals
;
3785 vec
<ipa_polymorphic_call_context
> known_contexts
;
3786 vec
<ipa_agg_jump_function_p
> known_aggs
;
3788 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3790 if (edge_growth_cache
.exists ())
3792 do_estimate_edge_time (edge
);
3793 size
= edge_growth_cache
[edge
->uid
].size
;
3794 gcc_checking_assert (size
);
3795 return size
- (size
> 0);
3798 callee
= edge
->callee
->ultimate_alias_target ();
3800 /* Early inliner runs without caching, go ahead and do the dirty work. */
3801 gcc_checking_assert (edge
->inline_failed
);
3802 evaluate_properties_for_edge (edge
, true,
3803 &clause
, &known_vals
, &known_contexts
,
3805 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3806 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3807 known_vals
.release ();
3808 known_contexts
.release ();
3809 known_aggs
.release ();
3814 /* Estimate the growth of the caller when inlining EDGE.
3815 Only to be called via estimate_edge_size. */
3818 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3821 struct cgraph_node
*callee
;
3823 vec
<tree
> known_vals
;
3824 vec
<ipa_polymorphic_call_context
> known_contexts
;
3825 vec
<ipa_agg_jump_function_p
> known_aggs
;
3827 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3829 if (edge_growth_cache
.exists ())
3831 do_estimate_edge_time (edge
);
3832 hints
= edge_growth_cache
[edge
->uid
].hints
;
3833 gcc_checking_assert (hints
);
3837 callee
= edge
->callee
->ultimate_alias_target ();
3839 /* Early inliner runs without caching, go ahead and do the dirty work. */
3840 gcc_checking_assert (edge
->inline_failed
);
3841 evaluate_properties_for_edge (edge
, true,
3842 &clause
, &known_vals
, &known_contexts
,
3844 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3845 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3846 known_vals
.release ();
3847 known_contexts
.release ();
3848 known_aggs
.release ();
3849 hints
|= simple_edge_hints (edge
);
3854 /* Estimate self time of the function NODE after inlining EDGE. */
3857 estimate_time_after_inlining (struct cgraph_node
*node
,
3858 struct cgraph_edge
*edge
)
3860 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3861 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3864 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3867 if (time
> MAX_TIME
)
3871 return inline_summaries
->get (node
)->time
;
3875 /* Estimate the size of NODE after inlining EDGE which should be an
3876 edge to either NODE or a call inlined into NODE. */
3879 estimate_size_after_inlining (struct cgraph_node
*node
,
3880 struct cgraph_edge
*edge
)
3882 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3883 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3885 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3886 gcc_assert (size
>= 0);
3889 return inline_summaries
->get (node
)->size
;
3895 struct cgraph_node
*node
;
3896 bool self_recursive
;
3902 /* Worker for do_estimate_growth. Collect growth for all callers. */
3905 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3907 struct cgraph_edge
*e
;
3908 struct growth_data
*d
= (struct growth_data
*) data
;
3910 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3912 gcc_checking_assert (e
->inline_failed
);
3914 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3916 d
->uninlinable
= true;
3920 if (e
->recursive_p ())
3922 d
->self_recursive
= true;
3925 d
->growth
+= estimate_edge_growth (e
);
3931 /* Estimate the growth caused by inlining NODE into all callees. */
3934 estimate_growth (struct cgraph_node
*node
)
3936 struct growth_data d
= { node
, false, false, 0 };
3937 struct inline_summary
*info
= inline_summaries
->get (node
);
3939 node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true);
3941 /* For self recursive functions the growth estimation really should be
3942 infinity. We don't want to return very large values because the growth
3943 plays various roles in badness computation fractions. Be sure to not
3944 return zero or negative growths. */
3945 if (d
.self_recursive
)
3946 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3947 else if (DECL_EXTERNAL (node
->decl
) || d
.uninlinable
)
3951 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3952 d
.growth
-= info
->size
;
3953 /* COMDAT functions are very often not shared across multiple units
3954 since they come from various template instantiations.
3955 Take this into account. */
3956 else if (DECL_COMDAT (node
->decl
)
3957 && node
->can_remove_if_no_direct_calls_p ())
3958 d
.growth
-= (info
->size
3959 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3966 /* Verify if there are fewer than MAX_CALLERS. */
3969 check_callers (cgraph_node
*node
, int *max_callers
)
3973 if (!node
->can_remove_if_no_direct_calls_and_refs_p ())
3976 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
3980 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3984 FOR_EACH_ALIAS (node
, ref
)
3985 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), max_callers
))
3992 /* Make cheap estimation if growth of NODE is likely positive knowing
3993 EDGE_GROWTH of one particular edge.
3994 We assume that most of other edges will have similar growth
3995 and skip computation if there are too many callers. */
3998 growth_likely_positive (struct cgraph_node
*node
,
4002 struct cgraph_edge
*e
;
4003 gcc_checking_assert (edge_growth
> 0);
4005 /* First quickly check if NODE is removable at all. */
4006 if (DECL_EXTERNAL (node
->decl
))
4008 if (!node
->can_remove_if_no_direct_calls_and_refs_p ()
4009 || node
->address_taken
)
4012 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
4014 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4018 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4023 FOR_EACH_ALIAS (node
, ref
)
4024 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), &max_callers
))
4027 /* Unlike for functions called once, we play unsafe with
4028 COMDATs. We can allow that since we know functions
4029 in consideration are small (and thus risk is small) and
4030 moreover grow estimates already accounts that COMDAT
4031 functions may or may not disappear when eliminated from
4032 current unit. With good probability making aggressive
4033 choice in all units is going to make overall program
4035 if (DECL_COMDAT (node
->decl
))
4037 if (!node
->can_remove_if_no_direct_calls_p ())
4040 else if (!node
->will_be_removed_from_program_if_no_direct_calls_p ())
4043 return estimate_growth (node
) > 0;
4047 /* This function performs intraprocedural analysis in NODE that is required to
4048 inline indirect calls. */
4051 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4053 ipa_analyze_node (node
);
4054 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4056 ipa_print_node_params (dump_file
, node
);
4057 ipa_print_node_jump_functions (dump_file
, node
);
4062 /* Note function body size. */
4065 inline_analyze_function (struct cgraph_node
*node
)
4067 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4070 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4071 node
->name (), node
->order
);
4072 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4073 inline_indirect_intraprocedural_analysis (node
);
4074 compute_inline_parameters (node
, false);
4077 struct cgraph_edge
*e
;
4078 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4080 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4081 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4082 e
->call_stmt_cannot_inline_p
= true;
4084 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4086 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4087 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4088 e
->call_stmt_cannot_inline_p
= true;
4096 /* Called when new function is inserted to callgraph late. */
4099 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4101 inline_analyze_function (node
);
4104 /* Note function body size. */
4107 inline_generate_summary (void)
4109 struct cgraph_node
*node
;
4111 FOR_EACH_DEFINED_FUNCTION (node
)
4112 if (DECL_STRUCT_FUNCTION (node
->decl
))
4113 node
->local
.versionable
= tree_versionable_function_p (node
->decl
);
4115 /* When not optimizing, do not bother to analyze. Inlining is still done
4116 because edge redirection needs to happen there. */
4117 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4120 if (!inline_summaries
)
4121 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4123 inline_summaries
->enable_insertion_hook ();
4125 ipa_register_cgraph_hooks ();
4126 inline_free_summary ();
4128 FOR_EACH_DEFINED_FUNCTION (node
)
4130 inline_analyze_function (node
);
4134 /* Read predicate from IB. */
4136 static struct predicate
4137 read_predicate (struct lto_input_block
*ib
)
4139 struct predicate out
;
4145 gcc_assert (k
<= MAX_CLAUSES
);
4146 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4150 /* Zero-initialize the remaining clauses in OUT. */
4151 while (k
<= MAX_CLAUSES
)
4152 out
.clause
[k
++] = 0;
4158 /* Write inline summary for edge E to OB. */
4161 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4163 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4167 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4168 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4169 es
->loop_depth
= streamer_read_uhwi (ib
);
4170 p
= read_predicate (ib
);
4171 edge_set_predicate (e
, &p
);
4172 length
= streamer_read_uhwi (ib
);
4175 es
->param
.safe_grow_cleared (length
);
4176 for (i
= 0; i
< length
; i
++)
4177 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4182 /* Stream in inline summaries from the section. */
4185 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4188 const struct lto_function_header
*header
=
4189 (const struct lto_function_header
*) data
;
4190 const int cfg_offset
= sizeof (struct lto_function_header
);
4191 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4192 const int string_offset
= main_offset
+ header
->main_size
;
4193 struct data_in
*data_in
;
4194 unsigned int i
, count2
, j
;
4195 unsigned int f_count
;
4197 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
,
4198 file_data
->mode_table
);
4201 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4202 header
->string_size
, vNULL
);
4203 f_count
= streamer_read_uhwi (&ib
);
4204 for (i
= 0; i
< f_count
; i
++)
4207 struct cgraph_node
*node
;
4208 struct inline_summary
*info
;
4209 lto_symtab_encoder_t encoder
;
4210 struct bitpack_d bp
;
4211 struct cgraph_edge
*e
;
4214 index
= streamer_read_uhwi (&ib
);
4215 encoder
= file_data
->symtab_node_encoder
;
4216 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4218 info
= inline_summaries
->get (node
);
4220 info
->estimated_stack_size
4221 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4222 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4223 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4225 bp
= streamer_read_bitpack (&ib
);
4226 info
->inlinable
= bp_unpack_value (&bp
, 1);
4227 info
->contains_cilk_spawn
= bp_unpack_value (&bp
, 1);
4229 count2
= streamer_read_uhwi (&ib
);
4230 gcc_assert (!info
->conds
);
4231 for (j
= 0; j
< count2
; j
++)
4234 c
.operand_num
= streamer_read_uhwi (&ib
);
4235 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4236 c
.val
= stream_read_tree (&ib
, data_in
);
4237 bp
= streamer_read_bitpack (&ib
);
4238 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4239 c
.by_ref
= bp_unpack_value (&bp
, 1);
4241 c
.offset
= streamer_read_uhwi (&ib
);
4242 vec_safe_push (info
->conds
, c
);
4244 count2
= streamer_read_uhwi (&ib
);
4245 gcc_assert (!info
->entry
);
4246 for (j
= 0; j
< count2
; j
++)
4248 struct size_time_entry e
;
4250 e
.size
= streamer_read_uhwi (&ib
);
4251 e
.time
= streamer_read_uhwi (&ib
);
4252 e
.predicate
= read_predicate (&ib
);
4254 vec_safe_push (info
->entry
, e
);
4257 p
= read_predicate (&ib
);
4258 set_hint_predicate (&info
->loop_iterations
, p
);
4259 p
= read_predicate (&ib
);
4260 set_hint_predicate (&info
->loop_stride
, p
);
4261 p
= read_predicate (&ib
);
4262 set_hint_predicate (&info
->array_index
, p
);
4263 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4264 read_inline_edge_summary (&ib
, e
);
4265 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4266 read_inline_edge_summary (&ib
, e
);
4269 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4271 lto_data_in_delete (data_in
);
4275 /* Read inline summary. Jump functions are shared among ipa-cp
4276 and inliner, so when ipa-cp is active, we don't need to write them
4280 inline_read_summary (void)
4282 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4283 struct lto_file_decl_data
*file_data
;
4286 inline_summary_alloc ();
4288 while ((file_data
= file_data_vec
[j
++]))
4291 const char *data
= lto_get_section_data (file_data
,
4292 LTO_section_inline_summary
,
4295 inline_read_section (file_data
, data
, len
);
4297 /* Fatal error here. We do not want to support compiling ltrans units
4298 with different version of compiler or different flags than the WPA
4299 unit, so this should never happen. */
4300 fatal_error (input_location
,
4301 "ipa inline summary is missing in input file");
4305 ipa_register_cgraph_hooks ();
4307 ipa_prop_read_jump_functions ();
4310 gcc_assert (inline_summaries
);
4311 inline_summaries
->enable_insertion_hook ();
4315 /* Write predicate P to OB. */
4318 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4322 for (j
= 0; p
->clause
[j
]; j
++)
4324 gcc_assert (j
< MAX_CLAUSES
);
4325 streamer_write_uhwi (ob
, p
->clause
[j
]);
4327 streamer_write_uhwi (ob
, 0);
4331 /* Write inline summary for edge E to OB. */
4334 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4336 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4339 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4340 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4341 streamer_write_uhwi (ob
, es
->loop_depth
);
4342 write_predicate (ob
, es
->predicate
);
4343 streamer_write_uhwi (ob
, es
->param
.length ());
4344 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4345 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4349 /* Write inline summary for node in SET.
4350 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4351 active, we don't need to write them twice. */
4354 inline_write_summary (void)
4356 struct cgraph_node
*node
;
4357 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4358 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4359 unsigned int count
= 0;
4362 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4364 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4365 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4366 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4369 streamer_write_uhwi (ob
, count
);
4371 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4373 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4374 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4375 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4377 struct inline_summary
*info
= inline_summaries
->get (node
);
4378 struct bitpack_d bp
;
4379 struct cgraph_edge
*edge
;
4382 struct condition
*c
;
4384 streamer_write_uhwi (ob
,
4385 lto_symtab_encoder_encode (encoder
,
4388 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4389 streamer_write_hwi (ob
, info
->self_size
);
4390 streamer_write_hwi (ob
, info
->self_time
);
4391 bp
= bitpack_create (ob
->main_stream
);
4392 bp_pack_value (&bp
, info
->inlinable
, 1);
4393 bp_pack_value (&bp
, info
->contains_cilk_spawn
, 1);
4394 streamer_write_bitpack (&bp
);
4395 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4396 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4398 streamer_write_uhwi (ob
, c
->operand_num
);
4399 streamer_write_uhwi (ob
, c
->code
);
4400 stream_write_tree (ob
, c
->val
, true);
4401 bp
= bitpack_create (ob
->main_stream
);
4402 bp_pack_value (&bp
, c
->agg_contents
, 1);
4403 bp_pack_value (&bp
, c
->by_ref
, 1);
4404 streamer_write_bitpack (&bp
);
4405 if (c
->agg_contents
)
4406 streamer_write_uhwi (ob
, c
->offset
);
4408 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4409 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4411 streamer_write_uhwi (ob
, e
->size
);
4412 streamer_write_uhwi (ob
, e
->time
);
4413 write_predicate (ob
, &e
->predicate
);
4415 write_predicate (ob
, info
->loop_iterations
);
4416 write_predicate (ob
, info
->loop_stride
);
4417 write_predicate (ob
, info
->array_index
);
4418 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4419 write_inline_edge_summary (ob
, edge
);
4420 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4421 write_inline_edge_summary (ob
, edge
);
4424 streamer_write_char_stream (ob
->main_stream
, 0);
4425 produce_asm (ob
, NULL
);
4426 destroy_output_block (ob
);
4428 if (optimize
&& !flag_ipa_cp
)
4429 ipa_prop_write_jump_functions ();
4433 /* Release inline summary. */
4436 inline_free_summary (void)
4438 struct cgraph_node
*node
;
4439 if (edge_removal_hook_holder
)
4440 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4441 edge_removal_hook_holder
= NULL
;
4442 if (edge_duplication_hook_holder
)
4443 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4444 edge_duplication_hook_holder
= NULL
;
4445 if (!inline_edge_summary_vec
.exists ())
4447 FOR_EACH_DEFINED_FUNCTION (node
)
4449 reset_inline_summary (node
, inline_summaries
->get (node
));
4450 inline_summaries
->release ();
4451 inline_summaries
= NULL
;
4452 inline_edge_summary_vec
.release ();
4453 edge_predicate_pool
.release ();